library(dplyr)
library(data.table)
library(cowplot)
library(ggraph)
library(igraph)
source("utils.R")
knitr::opts_chunk$set(
  fig.path = "decomposition_figs/",
  fig.keep = "high",
  dev = c("pdf", "png")
)
data.dir <- "../../data/"
source("load_data.R")
'measure.vars' [Abundance_e9312, Abundance_eMED4, Abundance_NATL, Abundancee_SS120, Abundancee_9313] are not all of the same type. By order of hierarchy, the molten data value column will be of type 'character'. All measure variables not of type 'character' will be coerced to. Check DETAILS in ?melt.data.table for more on coercion.NAs introduced by coercion

Prochloroccocus

BATS

Raw relative abundance time series of ecotypes at depths:

bats[, rel.abund := abundance / sum(abundance), by = depth]
bats[, log.rel.abund := log10(rel.abund)]
ggplot(bats, aes(x = month, y = log.rel.abund)) +
  geom_path(aes(group = ecotype)) +
  facet_grid(depth ~ ecotype) +
  theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1))

Power spectrum of ecotypes at depths:

# spectral analysis per ecotype per depth
# mean per month if more than one sample
bats.depthlra <- bats[, .(mn = mean(log.rel.abund)), 
                      by = .(month, depth, ecotype)]
bats.spec <- bats.depthlra[, {
  s <- stats::spectrum(mn, plot = FALSE)
  data.table(freq = s$freq, spec = s$spec)
  }, by = .(ecotype, depth)]
# normalize so peak is 1
bats.spec[, spec := spec / max(spec), by = .(depth, ecotype)]
bats.spec[, timescale.months := 1 / freq]
ggplot(bats.spec, aes(x = timescale.months, y = spec)) +
  geom_point(size = 0.5) +
  geom_path(aes(group = ecotype)) +
  facet_grid(depth ~ ecotype) +
  geom_vline(aes(linetype = "12"), xintercept = 12, color = "blue") +
  theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1))

Blue line indicates periodicity of 1 year. Relative height of peaks gives relative magnitude of periodic fluctuations at that time scale. This shows that not all ecotypes at all depths are most strongly driven by annual cycling. E.g. e9312 apparently experiences strong annual cycling at all depths except 100. NATL experiences annual cycling at all depths but it is relatively weaker at depths 160-200.

State clustering with JSD

setkey(bats, month)
# all pairs
bats[, id := paste(month, depth, sep = "_")]
bats.ids <- unique(bats$id)
bats.div <- MakeNonRedundantPairs(bats.ids, prefix = "id")
bats.div[, c("month.i", "depth.i") := tstrsplit(id.i, "_")]
bats.div[, c("month.j", "depth.j") := tstrsplit(id.j, "_")]
# it would be nice to get distances between depths but we'll do same depth rn
# down by order of magnitude
bats.div <- bats.div[depth.i == depth.j & month.j >= month.i]
bats.div[, depth.j := NULL]
setnames(bats.div, "depth.i", "depth")
setkey(bats, id)
bats.div[, jsd := {
  if (id.i == id.j) {
    0
  } else {
    # browser()
    sd <- bats[c(id.i, id.j)]
    sd <- dcast(sd, ecotype ~ id, value.var = "rel.abund", 
                fun.aggregate = mean)
    sd <- as.matrix(sd[, -1])
    genJSD(sd)
  }
  }, by = .(id.i, id.j)]
rec <- bats.div[id.i != id.j]
setnames(rec, names(rec), sapply(names(rec), function(str) {
  if (grepl("\\.i", str)) sub("\\.i", "\\.j", str)
  else if (grepl("\\.j", str)) sub("\\.j", "\\.i", str)
  else str
}))
bats.div <- rbind(bats.div, rec)
bats.div[, distance := sqrt(jsd)]
bats.div[, ":=" (month.i = as.numeric(month.i), 
                 month.j = as.numeric(month.j))]
bats.div[, delta := month.j - month.i]
vertices <- unique(bats[, .(id, month, cal.month, depth)])
# vertices[, depth := as.character(depth)]
edges <- bats.div[delta == 1, .(id.i, id.j, depth = as.numeric(depth))]
graph <- graph_from_data_frame(edges, directed = FALSE, vertices)
bats.depths <- unique(bats$depth)
bats.depths <- bats.depths[order(as.numeric(bats.depths))]
names(bats.depths) <- bats.depths
bats.dms <- lapply(bats.depths, function(de) {
  d <- bats.div[depth == de]
  MakeDistMatrix(d, "id.i", "id.j")
})
fits <- lapply(bats.dms, function(dm) {
  CoordCMDS(dm)
})
xforms <- lapply(fits, function(x) {
  x$points
}) %>% rbindlist(use.names = TRUE, idcol = "depth")
eigranks <- lapply(fits, function(x) {
  x$eigrank
}) %>% rbindlist(use.names = TRUE, idcol = "depth")
eigranks[, depth := factor(depth, levels = bats.depths)]
setkey(xforms, sample)
lo <- create_layout(graph, "manual", node.positions = xforms[V(graph)$name])
mbreaks <- c(1, 3, 6, 9, 12) # Jan, plus months of solstices + equinoxes
ggraph(lo) +
  geom_edge_link(arrow = arrow(type = "closed", length = unit(3, "points")),
                 end_cap = square(length = 3, unit = "points"),
                 edge_width = 0.2) +
  geom_node_point(aes(color = cal.month), size = 0.5) +
  scale_color_gradientn(values = scales::rescale(mbreaks),
                        colors = c("blue", "green4", "yellow", "orange",
                                   "blue")
                        ) +
  facet_wrap(~ depth, ncol = 3) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)

This also shows that seasonal cycling is more reproducible at some depths. For depths shallower than 100, there seems to be a reproducible path, and the composition seems to change more gradually, as can be seen in the close spacing of most consecutive timepoints. For depths 120-160, there are also reproducible paths, however, there are 3 clusters of time points (seemingly representing spring, summer/early fall, and late fall/winter) with large gaps between them, and the long leaps between clusters suggests the seasonal compositional transitions are more drastic. Finally, depths 180-200 appear more random.

Eigenvalues of MDS show that this transformation captures most of the information:

ggplot(eigranks, aes(x = rank, y = value ^2)) +
  geom_point() +
  scale_x_log10() +
  facet_wrap(~ depth, scales = "free_y")

Heatmapping the JSDs shows occupancy of stable states as dark squares of high temporal similarity along the diagonal. Recurrence of stable states show as dark off-diagonal rectangles. It is clear the time scales of stability (sizes of on-diagonal dark squares) are different for depths 1-40 and 100-160. 60-80 seem to be a hybrid of the two regimes, and 180-200 seem to go toward randomness.

bats.div[, depth := as.numeric(depth)]
ggplot(bats.div, aes(x = month.i, y = month.j)) +
  geom_tile(aes(fill = jsd)) + 
  facet_wrap(~ depth, ncol = 3) + 
  theme(aspect.ratio = 1)

David-style, JSD-based ‘autocorrelation.’ The periodicity of many of the autocorrelation functions shows strong periodic dynamics at a single time scale.

ggplot(bats.div[delta > 0], aes(x = delta, y = jsd)) +
  geom_point(size = 0.2) +
  geom_smooth() +
  facet_wrap(~ depth, ncol = 3) 

Dendrogram

For this dataset, the path plots might actually make the point more clearly/convincingly than the dendrogram wheels.

# clustering
bats.info[, month := as.character(month)]
setkey(bats.info, month)
bats.dendros <- lapply(bats.dms, function(dm) {
  hc <- hclust(dist(dm))
  dendro <- as.dendrogram(hc)
  dendro <- dendrapply(dendro, function(d) {
    if (is.leaf(d)) {
      labl <- attr(d, "label")
      mo <- strsplit(labl, "_")[[1]][1]
      cal.month <- unique(bats.info[mo, cal.month]) # for multiple passes/mo
      year <- unique(bats.info[mo, year]) # for multiple passes/mo
      attr(d, "nodePar") <- list(month = as.numeric(mo),
                                 cal.month = cal.month,
                                 year = year
      )
    }
    d
  })
  dendro <- tree_apply(dendro, function(node, children, depth, tree) {
    if(!is.leaf(node)) {
      child.months <- sapply(children, function(n) {
        attr(n, "nodePar")$cal.month
      })
      cal.month <- mean(child.months)
      attr(node, "nodePar") <- append(attr(node, "nodePar"),
                                      list(cal.month = cal.month))
    }
    node
  }, direction = "up")
  dendro
})
bats.los <- lapply(bats.dendros, function(dendro) {
  create_layout(dendro, "dendrogram", circular = TRUE)
})
bats.dendrographs <- lapply(bats.los, function(layout) {
  ggraph(layout) +
    geom_edge_elbow() +
    # geom_edge_elbow(aes(color = node2.cal.month)) +
    # scale_edge_color_gradientn(values = scales::rescale(mbreaks),
    #                       colors = c("blue", "green4", "yellow", "orange",
    #                                  "blue")) +
    theme_graph(base_family = "Helvetica") +
    geom_node_point(aes(filter = leaf, color = cal.month, 
                        shape = as.character(year)),
                    size = 1) +
    scale_color_gradientn(values = scales::rescale(mbreaks),
                          colors = c("blue", "green4", "yellow", "orange",
                                     "blue")) +
    theme_graph(base_family = "Helvetica") +
    theme(aspect.ratio = 1, legend.position = "none")
})
plot_grid(plotlist = bats.dendrographs, labels = names(bats.dendrographs),
          ncol = 3)

Coarse-graining states

Let the depth = 1 node ID be the state label of each time point. Again, this method doesn’t seem to give much extra information for this dataset. Perhaps there’s some other way to do this.

# create a unique ID for each state at depth = 2 and propagate down 
bats.dendros <- lapply(bats.dendros, function(dendro, thresh = 2) {
  # propagate up
  dendro <- tree_apply(dendro, function(node, children, depth, tree, th = thresh) {
    if (is.leaf(node)) {
      mo <- strsplit("_", attr(node, "label"))[[1]][[1]]
      state <- attr(node, "label")
    } else {
      if (depth >= th) {
        child.states <- sapply(children, function(d) attr(d, "nodePar")$state)
        # take the first child state as branch state
        state <- child.states[[1]]
      } else {
        state <- NA
      }
    }
    if (is.null (state)) browser()
    attr(node, "nodePar") <- append(attr(node, "nodePar"), list(state = state))
    node
  }, direction = "up")
  # propagate down
  dendro <- tree_apply(dendro, function(node, parent, depth, tree, th = thresh) {
    if (depth > th) {
      parstate <- attr(parent, "nodePar")$state
      attr(node, "nodePar")$state <- parstate
    }
    node
  })
  dendro
})
pl.bats.states <- lapply(bats.dendros, function(dendro) {
  ggraph(dendro, "dendrogram", circular = TRUE) +
  geom_edge_elbow(aes(color = node2.state)) +
  geom_node_point(aes(filter = leaf, 
                      color = cal.month),
                  size = 1
                  )+
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1, legend.position = "none") + 
  scale_color_gradientn(values = scales::rescale(mbreaks),
                        colors = c("blue", "green4", "yellow", "orange",
                                   "blue")) +
  guides(shape = guide_legend(ncol = 2),
         edge_colour = guide_legend(ncol = 2))
})
plot_grid(plotlist = pl.bats.states, ncol = 3, labels = names(pl.bats.states))

bats.samps2states <- lapply(bats.dendros, function(dendro) {
  graf <- den_to_igraph(dendro)
  islf <- V(graf)$leaf
  yr <- V(graf)$year[islf]
  mo <- V(graf)$month[islf]
  cm <- V(graf)$cal.month[islf]
  st <- V(graf)$state[islf]
  data.table(month = mo, year = yr, cal.month = cm, state = st)
}) %>% rbindlist(idcol = "depth")
ggplot(bats.samps2states, aes(x = cal.month, y = state, 
                              color = as.character(year))) +
  geom_line(aes(group = year)) +
  # geom_jitter(width = 0, height = 0.3) +
  labs(color = "year") +
  # theme(legend.position = "bottom") +
  facet_wrap(~ depth, scales = "free_y", ncol = 2)

Nahant

There are too many OTUs. They should probably be aggregated somehow. Here we aggregate all reads that map to the same phylum, which results in a manageable number of variables. But one could just as well aggregate at any other taxonomic level or not at all.

ggplot(eigranks, aes(x = rank, y = value ^2)) +
  geom_point() +
  scale_x_log10() +
  facet_wrap(~ depth, scales = "free_y")

phyla %>% 
  group_by(phylum) %>% 
  mutate(freq = scales::rescale(freq)) %>% 
  ggplot(aes(x = as.numeric(day), y = freq)) +
  theme(strip.text = element_text(size = 10),
        axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1)
        ) +
  scale_y_continuous(breaks = c(0, 0.5, 1)) +
  geom_line(aes(group = phylum)) +
  facet_wrap(~ phylum, ncol = 4) +
  labs(y = "frequency (normalized)")

We can look at the spectral density of the phyla time series. Phyla with peaks in the low frequencies exhibit slow fluctuations. It seems there really are slow and broad-spectrum taxa at this level.

phyla.spec <- phyla %>%
  dcast(day ~ phylum, value.var = "freq") %>% 
  select(-day) %>% 
  stats::spectrum(plot = FALSE)
phyla.spec <- data.table(cbind(phyla.spec$freq, phyla.spec$spec)) %>% 
  setnames(c("freq", phyla.spec$snames)) %>% 
  melt(id.vars = "freq", variable.name = "phylum")
phyla.spec %>% 
  group_by(phylum) %>% 
  mutate(value = value / sum(value)) %>% 
  ggplot(aes(x = freq, y = phylum)) +
  labs(x = "frequency (1/day)") +
  geom_tile(aes(fill = value)) 

R there statez?

Are there qualitative coarse-grainable compositional states in the Nahant data?

phyla[, day := as.character(day)]
days <- unique(phyla[, day])
day.div <- data.table(expand.grid(day.i = days, day.j = days))
day.div[, ":=" (day.i = as.character(day.i), 
                           day.j = as.character(day.j))]
setkey(phyla, day)
day.div[, jsd := {
  if (day.i == day.j) {
    0
  } else {
    sd <- phyla[c(day.i, day.j)]
    sd <- dcast(sd, phylum ~ day, value.var = "freq")
    m <- as.matrix(sd[, 2:3])
    d <- genJSD(m)
    d
  }
}, by = .(day.i, day.j)]
day.div[, distance := sqrt(jsd)]

Layout the samples by Jensen-Shannon distance using mds algorithm. Color by day so as to see temporal progression. Hierarchically cluster by JS distance.

edges <- cbind(days[-length(days)], days[-1])
graph <- graph_from_data_frame(edges, directed = FALSE,
                               vertices = data.table(id = days,
                                                     day = as.numeric(days)))
dm <- MakeDistMatrix(day.div, "day.i", "day.j")
fit <- CoordCMDS(dm)
xform <- fit$points
# order
setkey(xform, sample)
xform <- xform[V(graph)$name]
layout <- create_layout(graph, "manual", node.positions = xform)
p1 <- ggraph(layout) +
  geom_edge_link(arrow = arrow(type = "closed", 
                               length = unit(5, "points")),
                 edge_width = 0.2,
                 end_cap = square(length = 5, unit = "points")
                 ) +
  geom_node_point(aes(color = day)) +
  theme_graph(base_family = "Helvetica") +
  scale_color_distiller(palette = "Spectral") 
# clustering
hc <- hclust(dist(dm))
dendro <- as.dendrogram(hc)
dendro <- dendrapply(dendro, function(d) {
  if (is.leaf(d)) {
    attr(d, "nodePar") <- list(day = as.numeric(attr(d, "label")))
  }
  d
})
p2 <- ggraph(dendro, "dendrogram") +
  geom_edge_elbow() +
  # geom_node_text(aes(filter = leaf, color = day, label = day), angle = 90, size = 2) +
  geom_node_point(aes(filter = leaf, color = day)) +
  scale_color_distiller(palette = "Spectral") +
  theme_graph(base_family = "Helvetica") #+
  # theme(aspect.ratio = 1)
plot_grid(p1, p2, nrow = 2, align = "hv", labels = c("A", "B"))

These data show a clear transition between stable states around day 240. These two states form the two major branches at the lowest level of the hierarchical clustering.

The eigenvalues of the MDS transform show that information is well preserved:

ggplot(fit$eigrank, aes(x = rank, y = value ^ 2)) +
  geom_point()

Statistics of dynamics

Distribution of daily compositional step sizes. The Maxwell-Boltzmann/lognormal shape to the density at \(\Delta(t) = 1\) suggests that under this time resolution the change in composition behaves like some kind of random walk, with a characteristic step size and rare changes of larger magnitude.

day.div <- day.div[, day.delta := as.numeric(day.j) - as.numeric(day.i)]
p1 <- ggplot(day.div[day.delta == 1,], aes(x = distance)) +
  stat_bin(bins = 30) 
p2 <- ggplot(day.div[day.delta == 1], aes(x = as.numeric(day.i), y = distance)) +
  geom_point() + 
  # stat_smooth() + 
  labs(x = "day i")
plot_grid(p1, p2, nrow = 2, labels = "AUTO", align = "hv")

day.div[day.delta > 0] %>% 
  mutate(group = as.factor(floor(day.delta / 10) * 10),
         ddelta = as.factor(day.delta %% 10)) %>% 
  ggplot(aes(x = distance)) +
  stat_bin(bins = 30, position = "identity") +
  scale_color_brewer(palette = "Spectral") +
  theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1, 
                                   size = 7
                                   ),
        axis.text.y = element_text(size = 6)
        ) +
  facet_grid(group ~ ddelta, scales = "free_y")

Compositional distance as function of interval. This is sort of an autocorrelation spectrum. There are no peaks in this ‘spectrum’ suggesting there are no characteristic time scales of periodic behavior. Since there is only one major state transition in these data, it could also be interpreted as the period of state transitions being longer than the observation time, when interpreted as periodic.

br <- days[seq(1, length(days), by = 5)]
ggplot(day.div, aes(x = day.i, y = day.j)) +
  geom_tile(aes(fill = distance)) +
  scale_x_discrete(breaks = br) +
  scale_y_discrete(breaks = br) +
  theme(aspect.ratio = 1,
        axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1))

tl <- day.div[day.delta > 0, .(mn.dist = mean(distance)), by = day.delta]
p0 <- ggplot(day.div[day.delta > 0], aes(x = day.delta, y = distance)) 
p1 <- p0 + geom_point(size = 1) + 
  # stat_smooth(aes(linetype = "mean"))  +
  geom_line(aes(y = mn.dist, linetype = "mean"), tl, color = "blue", size = 2) +
  labs(linetype = "", x = "interval (days)")
p2 <- p0 + stat_bin_2d(binwidth = c(1, 0.01)) + labs(x = "interval (days)")
plot_grid(p1, p2, nrow = 2, align = "hv", labels = "AUTO")

Human

David et al

david <- fread(paste0(data.dir, "david/david.otus"), 
               col.names = c("sample", "otu", "count")
               )
# parse subject and timepoints
david.samples <- unique(david[, .(sample)])
david.samples[, c("subject", "day") := tstrsplit(sample, "_")]
# log transform otu counts
david[, log.count := log(count + 1)]
# split by subject
david.subjects <- unique(david.samples$subject)
names(david.subjects) <- david.subjects
# create tables of day-day divergences
david.div <- data.table(expand.grid(sample.i = david.samples$sample,
                                    sample.j = david.samples$sample)
                        )
david.samples[, idx := 1:.N]
david.samples[, subj.idx := frank(as.numeric(day)), by = subject]
david.div <- merge(david.div, david.samples, by.x = "sample.i", 
                   by.y = "sample")
david.div <- merge(david.div, david.samples, by.x = "sample.j", 
                   by.y = "sample", suffixes = c(".i", ".j"))
david.div <- david.div[idx.j >= idx.i]
setkey(david, sample)
david.div[, jsd := {
  if (sample.i == sample.j) {
    0
  } else {
    sd <- david[c(sample.i, sample.j)]
    m <- dcast(sd, otu ~ sample, value.var = "count")
    m <- as.matrix(m[, 2:3])
    m[is.na(m)] <- 0
    genJSD(m)
  }
}, by = .(sample.i, sample.j)]
# reciprocal distances
david.div <- david.div[sample.i != sample.j] %>% 
  setnames(names(david.div), sapply(names(david.div), function(x) {
    if (grepl("idx\\.i", x)) {
      gsub("idx\\.i", "idx\\.j", x)
    } else if (grepl("idx\\.j", x)) {
      gsub("idx\\.j", "idx\\.i", x)
    } else if (grepl("\\.i", x)) {
      gsub("\\.i", "\\.j", x)
    } else if (grepl("\\.j", x)) {
      gsub("\\.j", "\\.i", x)
    } else x
  })
  ) %>%  
  rbind(david.div)
david.div[, distance := sqrt(jsd)]
david.div[, day.delta := as.numeric(day.j) - as.numeric(day.i)]
david.div[subject.i == subject.j, increment := subj.idx.j - subj.idx.i]

Merge event metadata:

david <- fread(paste0(data.dir, "david/david.otus"), 
               col.names = c("sample", "otu", "count")
               )
# parse subject and timepoints
david.samples <- unique(david[, .(sample)])
david.samples[, c("subject", "day") := tstrsplit(sample, "_")]
# log transform otu counts
david[, log.count := log(count + 1)]
# split by subject
david.subjects <- unique(david.samples$subject)
names(david.subjects) <- david.subjects
# create tables of day-day divergences
david.div <- data.table(expand.grid(sample.i = david.samples$sample,
                                    sample.j = david.samples$sample)
                        )
david.samples[, idx := 1:.N]
david.samples[, subj.idx := frank(as.numeric(day)), by = subject]
david.div <- merge(david.div, david.samples, by.x = "sample.i", 
                   by.y = "sample")
david.div <- merge(david.div, david.samples, by.x = "sample.j", 
                   by.y = "sample", suffixes = c(".i", ".j"))
david.div <- david.div[idx.j >= idx.i]
setkey(david, sample)
david.div[, jsd := {
  if (sample.i == sample.j) {
    0
  } else {
    sd <- david[c(sample.i, sample.j)]
    m <- dcast(sd, otu ~ sample, value.var = "count")
    m <- as.matrix(m[, 2:3])
    m[is.na(m)] <- 0
    genJSD(m)
  }
}, by = .(sample.i, sample.j)]
# reciprocal distances
david.div <- david.div[sample.i != sample.j] %>% 
  setnames(names(david.div), sapply(names(david.div), function(x) {
    if (grepl("idx\\.i", x)) {
      gsub("idx\\.i", "idx\\.j", x)
    } else if (grepl("idx\\.j", x)) {
      gsub("idx\\.j", "idx\\.i", x)
    } else if (grepl("\\.i", x)) {
      gsub("\\.i", "\\.j", x)
    } else if (grepl("\\.j", x)) {
      gsub("\\.j", "\\.i", x)
    } else x
  })
  ) %>%  
  rbind(david.div)
david.div[, distance := sqrt(jsd)]
david.div[, day.delta := as.numeric(day.j) - as.numeric(day.i)]
david.div[subject.i == subject.j, increment := subj.idx.j - subj.idx.i]

The magnitudes of day-to-day changes in composition don’t reflect significant events.

setkey(david.div, subject.i, subject.j)
event.lims <- events[, .(start = min(day), end = max(day)), 
                     by = .(event, subject)]
event.lims <- event.lims[!grepl("pre", event) & !grepl("post", event)]
event.lims[, event := factor(levels = c("travel", "diarrhea 1", "diarrhea 2",
                                        "Salmonella"), event)]
david.div[subject.i == subject.j & day.delta == 1] %>% 
  mutate(day.i = as.numeric(day.i)) %>% 
  setnames("subject.i", "subject") %>% 
  ggplot(aes(x = day.i, y = distance)) +
  geom_rect(data = event.lims, 
    mapping = aes(fill = event, xmin = start, xmax = end, 
                  ymin = 0.1, ymax = 1.05
                  ), inherit.aes = FALSE, alpha = 0.5) +
  geom_point() +
  facet_wrap(~ subject, nrow = 2)

Distributions of all distances for all time scales. We see that both length distributions are multimodal, indicating at least 2 compositional “length scales.” We also see that the vast majority of A distances belong to the lowest mode, while the second lowest mode of B is as high as the lowest, indicating that subject B spends a significant amount of time (relative to the length of the entire measurement).

p0 <- ggplot(david.div[subject.i == subject.j], aes(x = distance)) 
ar <- 3 / 5
cdf <- p0 + stat_ecdf(aes(color = subject.i)) + labs(y = "ECDF") +
  theme(aspect.ratio = ar)
dens <- p0 + stat_density(aes(fill = subject.i), alpha = 0.5, 
                          position = "identity") +
  theme(aspect.ratio = ar)
plot_grid(cdf, dens, nrow = 2, align = "v")

Paths

david.subjects <- c("A", "B")
names(david.subjects) <- david.subjects
setkey(david.div, subject.i, subject.j)
dm <- MakeDistMatrix(david.div, "sample.i", "sample.j")
fit <- CoordCMDS(dm)
xform <- fit$points
setcolorder(xform, c("sample", "x", "y"))
setkey(xform, sample)
# put sample labels at first 2 columns
setcolorder(david.div, c("sample.i", "sample.j",
                         names(david.div)[!(names(david.div) %in%
                                              c("sample.i", "sample.j"))])
            )
david.samples[, day := as.numeric(day)]
setcolorder(david.samples, c("sample", "subject", "day", "event", "idx", 
                             "subj.idx"))
graf <- graph_from_data_frame(
  david.div[subject.i == subject.j & increment == 1],
  directed = TRUE,
  vertices = david.samples
  )
setkey(xform, sample)
xform <- xform[V(graf)$name]
lo <- create_layout(graf, "manual", node.positions = xform)
nsize <- 1
p1 <- ggraph(lo) +
  geom_edge_link(arrow = arrow(length = unit(3, "points"), type = "closed"),
                 end_cap = square(length = 3, unit = "points"),
                 edge_width = 0.2) +
  geom_node_point(aes(color = day), size = nsize) +
  scale_color_distiller(palette = "Blues") +
  facet_nodes(~ subject) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)
p2 <- ggraph(lo) +
  geom_edge_link(arrow = arrow(length = unit(3, "points"), type = "closed"),
                 end_cap = square(length = 3, unit = "points"),
                 edge_width = 0.2) +
  geom_node_point(aes(color = event), size = nsize) +
  facet_nodes(~ subject) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)
plot_grid(p1, p2, nrow = 2, align = "v")

Laying both subjects along the same axes we see each subject is more similar to themselves than they are to the other subject, for the most part. The upper right represents states in which the two subjects resembled each other. Interestingly not all these points seem to be close in time. Subject B makes a brief excursion to a Subject A-like state post Salmonella.

Eigenvalues by rank:

ggplot(fit$eigrank, aes(x = rank, y = value ^ 2)) +
  geom_point()

Trees

Together

Hierarchical clustering reveals 3 major branches: characteristic of Subject A, characteristic of Subject B, and Shared Outlier State.

dm <- dcast(david.div, sample.i ~ sample.j, value.var = "distance")
rn <- dm$sample.i
dm <- dm[, -1]
dm <- as.matrix(dm)
rownames(dm) <- rn
dendro <- as.dendrogram(hclust(dist(dm)))
unique.day.events[, day := as.character(day)]
setkey(unique.day.events, subject, day)
david.samples[, day := as.character(day)]
david.samples[, state := {
  subj <- subject
  dd <- day
  unique.day.events[.(subj, dd), event]
}, by = .(subject, day)]
setkey(david.samples, sample)
dendro <- dendrapply(dendro, function(d) {
  if (is.leaf(d)) {
    samp <- attr(d, "label")
    subj <- david.samples[samp, subject]
    state <- david.samples[samp, state]
    attr(d, "nodePar") <- append(attr(d, "nodePar"), list(subject = subj, 
                                                          state = state))
  }
  d
})
ggraph(dendro, "dendrogram") +
  geom_edge_elbow() +
  geom_node_point(aes(filter = leaf, shape = subject, color = state), size = 1) +
  theme_graph(base_family = "Helvetica") +
  # theme(aspect.ratio = 1) + 
  coord_flip()

Separate

Clustering separately shows that Subject B has distinct pre- and post-Salmonella states, but the various events in Subject A’s life didn’t create alternate stable states that were significantly different.

setkey(david.div, subject.i, subject.j)
dendros <- lapply(david.subjects, function(subj) {
  sd <- david.div[.(subj, subj)]
  dm <- dcast(sd, sample.i ~ sample.j, value.var = "distance")
  rn <- dm$sample.i
  dm <- dm[, -1]
  dm <- as.matrix(dm)
  rownames(dm) <- rn
  hc <- hclust(dist(dm))
  dendro <- as.dendrogram(hc)
  return(dendro)
}
)
unique.day.events[, day := as.character(day)]
# setkey(events, subject)
setkey(unique.day.events, subject, day)
setkey(david.samples, sample)
dendros <- lapply(david.subjects, function(subj) {
  dendro <- dendros[[subj]]
  dendro <- dendrapply(dendro, function(d) {
    if (is.leaf(d)) {
      dday <- david.samples[attr(d, "label"), as.character(day)]
      ev <- unique.day.events[.(subj, dday), event]
      attr(d, "nodePar") <- append(attr(d, "nodePar"), list(
        day = as.numeric(dday),
        event = ev))
    }
    d
  })
  # propagate metadata back up the tree
  dendro <- tree_apply(dendro, function(node, children, depth, tree) {
  if (!is.leaf(node)) {
    events <- sapply(children, function(c) {
      attr(c, "nodePar")$event
    })
    events <- unique(events)
    if (length(events) == 1 & !anyNA(events)) {
      attr(node, "nodePar") <- append(attr(node, "nodePar"), list(event = events))
    } else {
      attr(node, "nodePar") <- append(attr(node, "nodePar"), list(event = NA))
    }
  }
  node
  }, direction = "up")
  dendro
})
dendro.plots <- lapply(dendros, function(dend) {
  ggraph(dend, "dendrogram", circular = TRUE) +
    geom_edge_elbow(aes(color = node2.event)) +
    geom_node_point(aes(filter = leaf, color = day), size = 0.6) +
    scale_color_distiller(palette = "Spectral") +
    theme_graph(base_family = "Helvetica") +
    theme(aspect.ratio = 1)
})
plot_grid(plotlist = dendro.plots, nrow = 2, labels = "AUTO")

Subject A doesn’t seem to have a distinct “traveling” composition. Indeed it seems the distance between traveling and US compositions doesn’t seem noticeably larger than the distance between US compositions. Meaning traveling did not destabilize the microbiome any more than baseline fluctuations while living in the US. Perhaps this is due to many OTUs remaining stable through the duration of travel.

Subject B shows clear pre- and post-Salmonella states, as reported in the original manuscript. Perhaps the post-Salmonella state is separate because of the extinction of cluster 4 (see original paper) during infection, rendering return to the pre-Salmonella state impossible?

Gordon et al (cholera)

# metadata
setkey(david.samples, subject)
events <- mapply(function(start, end, subject, event) {
  x <- data.table(day = seq(start, end, by = 1), subject = subject, 
                  event = event)
  x
}, start = c(0, 71, 80, 104, 123, 
             0, 151, 160 ),
end =   c(70, 122, 85, 113, david.samples["A", max(as.numeric(day))], 
          150, 159, david.samples["B", max(as.numeric(day))]),
subject = c("A", "A", "A", "A", "A", 
            "B", "B", "B"),
event = c("US (pre)", "travel", "diarrhea 1", "diarrhea 2", "US (post)", 
          "pre-Salmonella", "Salmonella", "post-Salmonella"),
SIMPLIFY = FALSE) %>% rbindlist(use.names = TRUE) 
# collapse event labels per day
unique.day.events <- events[, .(event = paste(event, collapse = " + ")), 
                           by = .(subject, day)]
unique.day.events[, day := as.character(day)]
david.samples <- merge(david.samples, unique.day.events, 
                       by = c("subject", "day"))
david.div <- merge(david.div, unique.day.events, by.x = c("subject.i", "day.i"),
                   by.y = c("subject", "day"))
david.div <- merge(david.div, unique.day.events, by.x = c("subject.j", "day.j"),
                   by.y = c("subject", "day"), suffixes = c(".i", ".j"))

David-style divergence matrices. Dark on-diagonal squares represent occupation of stable states. Most patients have distinct stable states.

setkey(gordon.div, subject.i, subject.j)
subjects <- sort(subjects)
names(subjects) <- subjects
gordon.div[, ":=" (hour.i = as.character(hour.i), hour.j = as.character(hour.j))]
plots <- lapply(subjects, function(subj) {
  sd <- gordon.div[.(subj, subj)]
  ts <- as.numeric(unique(sd$hour.i))
  lims <- as.character(sort(ts))
  p <- ggplot(sd, aes(x = hour.i, y = hour.j)) +
    geom_tile(aes(fill = jsd)) +
    scale_x_discrete(limits = lims) +
    scale_y_discrete(limits = lims) +
    theme(aspect.ratio = 1,
          axis.text = element_blank(),
          axis.ticks = element_blank())
})
plot_grid(plotlist = plots, ncol = 2, labels = names(plots), align = "hv")

Time-lag divergences:

gordon.div[, delta.t := as.numeric(hour.j) - as.numeric(hour.i)]
plots <- lapply(subjects, function(subj) {
  sd <- gordon.div[.(subj, subj)]
  sd <- sd[delta.t > 0]
  p <- ggplot(sd, aes(x = delta.t, y = jsd)) +
    geom_point(size = 0.1) +
    geom_smooth(color = "blue") +
    scale_x_log10() +
    labs(x = "lag (hours)")
  p
})
plot_grid(plotlist = plots, align = "hv", labels = names(plots),
          nrow = 3)
`geom_smooth()` using method = 'gam'
`geom_smooth()` using method = 'loess'
`geom_smooth()` using method = 'loess'
`geom_smooth()` using method = 'loess'
`geom_smooth()` using method = 'loess'
`geom_smooth()` using method = 'loess'
`geom_smooth()` using method = 'loess'

Distributions of divergences show that for all patients, diarrhea and recovery states are more similar to themselves than to each other (cross-state divergences are large). In most patients (except E) the recovery microbiome is actually less stable than the diarrhea microbiome: the diarrhea divergences tend to be smaller. However this could also be due to the denser temporal sampling during the diarrhea period. We should scale this by the time interval somehow, since it varies.

gordon.div[, state := {
  if (state.i == state.j) state.i
  else "cross"
}, by = .(state.i, state.j)]  
p0 <- gordon.div[(subject.i == subject.j) & (delta.t > 0)] %>% 
  ggplot(aes(x = distance))
cdf <- p0 + stat_ecdf(aes(color = state)) + facet_wrap(~ subject.i, nrow = 1) + 
  labs(y = "ECDF") +
  theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1))
dens <- p0 + stat_density(aes(fill = state), alpha = 0.3,
                          position = "identity")
dens <- dens +
  facet_wrap(~ subject.i, nrow = 1) +
  theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1))
plot_grid(cdf, dens, nrow = 2, align = "v")

Paths

MDS of all subjects simultaneously shows that diarrhea/recovery separates time points more than subject.

setkey(gordon.div, subject.i, subject.j)
setkey(gordon.samples, subject)
edges <- lapply(subjects, function(subj) {
  sd <- gordon.div[.(subj, subj)]
  ts <- as.numeric(unique(sd$hour.i))
  ts <- as.character(sort(ts))
  ej <- data.table(ti = ts[-length(ts)], tj = ts[-1])
  samps <- gordon.samples[subj, .(sample, hour)]
  samps[, hour := as.character(hour)]
  ej <- merge(ej, samps, by.x = "ti", by.y = "hour")
  ej <- merge(ej, samps, by.x = "tj", by.y = "hour", suffixes = c(".i", ".j"))
  ej[, .(sample.i, sample.j)]
}) %>% rbindlist()
graf <- graph_from_data_frame(edges,
                              directed = TRUE, vertices = gordon.samples)
dm <- MakeDistMatrix(gordon.div, "sample.i", "sample.j")
fit <- CoordCMDS(dm)
xform <- fit$points
# order
setkey(xform, sample)
xform <- xform[V(graf)$name]
lo <- create_layout(graf, "manual", node.positions = xform)
ggraph(lo) +
  geom_edge_link(arrow = arrow(type = "closed", length = unit(3, "points")),
                 edge_width = 0.2, end_cap = square(length = 3,
                                                    unit = "points")) +
  geom_node_point(aes(color = state)) +
  # scale_shape_manual(values = seq(1, length(subjects))) +
  facet_nodes(~ subject, nrow = 2) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)

ggplot(fit$eigrank, aes(x = rank, y = value ^ 2)) +
  geom_point() 

All points plot show recovery and diarrhea cluster separately for all patients, with diarrhea having greater spread:

ggraph(lo) +
  geom_node_point(aes(color = state, shape = subject)) +
  scale_shape_manual(values = seq(uniqueN(gordon.samples$subject))) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)

Tree

All together. Again separation is mostly diarrhea/recovery. However, some diarrhea points are closer to recovery points than they are to the majority of diarrhea points. This can also be seen in the last plot where the two ‘clouds’ enmesh.

ggraph(lo) +
  geom_node_point(aes(color = state, shape = subject)) +
  scale_shape_manual(values = seq(uniqueN(gordon.samples$subject))) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)

setkey(gordon.div, subject.i, subject.j)
gordon.samples[, hour := as.character(hour)]
setkey(gordon.samples, subject, hour)
trees <- lapply(subjects, function(subj) {
  sd <- gordon.div[.(subj, subj)]
  sd <- dcast(sd, hour.i ~ hour.j, value.var = "distance")
  rn <- sd[, hour.i]
  dm <- as.matrix(sd[, -1])
  rownames(dm) <- rn
  dendro <- as.dendrogram(hclust(dist(dm)))
  # merge time data and state
  sd[, time.index := frank(as.numeric(hour.i))]
  setkey(sd, hour.i)
  dendro <- dendrapply(dendro, function(node) {
    if (is.leaf(node)) {
      labl <- attr(node, "label")
      t <- as.numeric(labl)
      time.index <- as.numeric(sd[labl, time.index])
      state <- gordon.samples[.(subj, labl), state]
      attr(node, "nodePar") <- append(attr(node, "nodePar"), 
                                      list(hour = t, time.index = time.index,
                                           state = state)
                                      )
    }
    node
  })
  # propagate state upwards through branch nodes
  dendro <- tree_apply(dendro, function(node, tree, depth, children) {
    if (!is.leaf(node)) {
      child.states <- sapply(children, function(n) {
        attr(n, "nodePar")$state
      }) %>% unique()
      if (length(child.states) == 1 & !anyNA(child.states)) {
        state <- child.states
      } else {
        state <- NA
      }
      attr(node, "nodePar") <- append(attr(node, "nodePar"),
                                      list(state = state))
    }
    node
  }, direction = "up")
  # browser()
  p <- ggraph(dendro, "dendrogram", circular = TRUE) +
    geom_edge_elbow(aes(color = node2.state)) +
    geom_node_point(aes(filter = leaf, color = time.index)) +
    scale_color_distiller(palette = "YlOrRd") +
    theme_graph(base_family = "Helvetica") +
    theme(aspect.ratio = 1, legend.key.height = unit(10, "points"))
})
plot_grid(plotlist = trees, ncol = 2, labels = names(trees))

LS0tCnRpdGxlOiAiRGVjb21wb3NpdGlvbiBvZiB0aW1lIHNjYWxlcyBpbiBtaWNyb2JpYWwgdGltZSBzZXJpZXMiCm91dHB1dDoKICBodG1sX25vdGVib29rOiBkZWZhdWx0CiAgaHRtbF9kb2N1bWVudDoKICAgIHRvYzogeWVzCiAgICB0b2NfZGVwdGg6IDIKICAgIHRvY19mbG9hdDogeWVzCiAgcGRmX2RvY3VtZW50OiBkZWZhdWx0Ci0tLQoKYGBge3Igc2V0dXAsIG1lc3NhZ2U9RkFMU0V9CmxpYnJhcnkoZHBseXIpCmxpYnJhcnkoZGF0YS50YWJsZSkKbGlicmFyeShjb3dwbG90KQpsaWJyYXJ5KGdncmFwaCkKbGlicmFyeShpZ3JhcGgpCnNvdXJjZSgidXRpbHMuUiIpCmtuaXRyOjpvcHRzX2NodW5rJHNldCgKICBmaWcucGF0aCA9ICJkZWNvbXBvc2l0aW9uX2ZpZ3MvIiwKICBmaWcua2VlcCA9ICJoaWdoIiwKICBkZXYgPSBjKCJwZGYiLCAicG5nIikKKQpkYXRhLmRpciA8LSAiLi4vLi4vZGF0YS8iCnNvdXJjZSgibG9hZF9kYXRhLlIiKQpgYGAKCiMgUHJvY2hsb3JvY2NvY3VzCgojIyBCQVRTClJhdyByZWxhdGl2ZSBhYnVuZGFuY2UgdGltZSBzZXJpZXMgb2YgZWNvdHlwZXMgYXQgZGVwdGhzOgpgYGB7ciBiYXRzLXRzLGZpZy53aWR0aD03LGZpZy5oZWlnaHQ9N30KYmF0c1ssIHJlbC5hYnVuZCA6PSBhYnVuZGFuY2UgLyBzdW0oYWJ1bmRhbmNlKSwgYnkgPSBkZXB0aF0KYmF0c1ssIGxvZy5yZWwuYWJ1bmQgOj0gbG9nMTAocmVsLmFidW5kKV0KZ2dwbG90KGJhdHMsIGFlcyh4ID0gbW9udGgsIHkgPSBsb2cucmVsLmFidW5kKSkgKwogIGdlb21fcGF0aChhZXMoZ3JvdXAgPSBlY290eXBlKSkgKwogIGZhY2V0X2dyaWQoZGVwdGggfiBlY290eXBlKSArCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA5MCwgdmp1c3QgPSAwLjUsIGhqdXN0ID0gMSkpCmBgYAoKUG93ZXIgc3BlY3RydW0gb2YgZWNvdHlwZXMgYXQgZGVwdGhzOgpgYGB7ciBiYXRzLXNwZWMsIGZpZy5hc3A9MX0KIyBzcGVjdHJhbCBhbmFseXNpcyBwZXIgZWNvdHlwZSBwZXIgZGVwdGgKIyBtZWFuIHBlciBtb250aCBpZiBtb3JlIHRoYW4gb25lIHNhbXBsZQpiYXRzLmRlcHRobHJhIDwtIGJhdHNbLCAuKG1uID0gbWVhbihsb2cucmVsLmFidW5kKSksIAogICAgICAgICAgICAgICAgICAgICAgYnkgPSAuKG1vbnRoLCBkZXB0aCwgZWNvdHlwZSldCmJhdHMuc3BlYyA8LSBiYXRzLmRlcHRobHJhWywgewogIHMgPC0gc3RhdHM6OnNwZWN0cnVtKG1uLCBwbG90ID0gRkFMU0UpCiAgZGF0YS50YWJsZShmcmVxID0gcyRmcmVxLCBzcGVjID0gcyRzcGVjKQogIH0sIGJ5ID0gLihlY290eXBlLCBkZXB0aCldCiMgbm9ybWFsaXplIHNvIHBlYWsgaXMgMQpiYXRzLnNwZWNbLCBzcGVjIDo9IHNwZWMgLyBtYXgoc3BlYyksIGJ5ID0gLihkZXB0aCwgZWNvdHlwZSldCmJhdHMuc3BlY1ssIHRpbWVzY2FsZS5tb250aHMgOj0gMSAvIGZyZXFdCmdncGxvdChiYXRzLnNwZWMsIGFlcyh4ID0gdGltZXNjYWxlLm1vbnRocywgeSA9IHNwZWMpKSArCiAgZ2VvbV9wb2ludChzaXplID0gMC41KSArCiAgZ2VvbV9wYXRoKGFlcyhncm91cCA9IGVjb3R5cGUpKSArCiAgZmFjZXRfZ3JpZChkZXB0aCB+IGVjb3R5cGUpICsKICBnZW9tX3ZsaW5lKGFlcyhsaW5ldHlwZSA9ICIxMiIpLCB4aW50ZXJjZXB0ID0gMTIsIGNvbG9yID0gImJsdWUiKSArCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA5MCwgdmp1c3QgPSAwLjUsIGhqdXN0ID0gMSkpCmBgYApCbHVlIGxpbmUgaW5kaWNhdGVzIHBlcmlvZGljaXR5IG9mIDEgeWVhci4KUmVsYXRpdmUgaGVpZ2h0IG9mIHBlYWtzIGdpdmVzIHJlbGF0aXZlIG1hZ25pdHVkZSBvZiBwZXJpb2RpYyBmbHVjdHVhdGlvbnMgYXQgdGhhdCB0aW1lIHNjYWxlLgpUaGlzIHNob3dzIHRoYXQgbm90IGFsbCBlY290eXBlcyBhdCBhbGwgZGVwdGhzIGFyZSBtb3N0IHN0cm9uZ2x5IGRyaXZlbiBieSBhbm51YWwgY3ljbGluZy4KRS5nLiBlOTMxMiBhcHBhcmVudGx5IGV4cGVyaWVuY2VzIHN0cm9uZyBhbm51YWwgY3ljbGluZyBhdCBhbGwgZGVwdGhzIGV4Y2VwdCAxMDAuCk5BVEwgZXhwZXJpZW5jZXMgYW5udWFsIGN5Y2xpbmcgYXQgYWxsIGRlcHRocyBidXQgaXQgaXMgcmVsYXRpdmVseSB3ZWFrZXIgYXQgZGVwdGhzIDE2MC0yMDAuCgojIyBTdGF0ZSBjbHVzdGVyaW5nIHdpdGggSlNECmBgYHtyIGJhdHMtc3RhdGVzfQpzZXRrZXkoYmF0cywgbW9udGgpCiMgYWxsIHBhaXJzCmJhdHNbLCBpZCA6PSBwYXN0ZShtb250aCwgZGVwdGgsIHNlcCA9ICJfIildCmJhdHMuaWRzIDwtIHVuaXF1ZShiYXRzJGlkKQpiYXRzLmRpdiA8LSBNYWtlTm9uUmVkdW5kYW50UGFpcnMoYmF0cy5pZHMsIHByZWZpeCA9ICJpZCIpCmJhdHMuZGl2WywgYygibW9udGguaSIsICJkZXB0aC5pIikgOj0gdHN0cnNwbGl0KGlkLmksICJfIildCmJhdHMuZGl2WywgYygibW9udGguaiIsICJkZXB0aC5qIikgOj0gdHN0cnNwbGl0KGlkLmosICJfIildCiMgaXQgd291bGQgYmUgbmljZSB0byBnZXQgZGlzdGFuY2VzIGJldHdlZW4gZGVwdGhzIGJ1dCB3ZSdsbCBkbyBzYW1lIGRlcHRoIHJuCiMgZG93biBieSBvcmRlciBvZiBtYWduaXR1ZGUKYmF0cy5kaXYgPC0gYmF0cy5kaXZbZGVwdGguaSA9PSBkZXB0aC5qICYgbW9udGguaiA+PSBtb250aC5pXQpiYXRzLmRpdlssIGRlcHRoLmogOj0gTlVMTF0Kc2V0bmFtZXMoYmF0cy5kaXYsICJkZXB0aC5pIiwgImRlcHRoIikKc2V0a2V5KGJhdHMsIGlkKQpiYXRzLmRpdlssIGpzZCA6PSB7CiAgaWYgKGlkLmkgPT0gaWQuaikgewogICAgMAogIH0gZWxzZSB7CiAgICAjIGJyb3dzZXIoKQogICAgc2QgPC0gYmF0c1tjKGlkLmksIGlkLmopXQogICAgc2QgPC0gZGNhc3Qoc2QsIGVjb3R5cGUgfiBpZCwgdmFsdWUudmFyID0gInJlbC5hYnVuZCIsIAogICAgICAgICAgICAgICAgZnVuLmFnZ3JlZ2F0ZSA9IG1lYW4pCiAgICBzZCA8LSBhcy5tYXRyaXgoc2RbLCAtMV0pCiAgICBnZW5KU0Qoc2QpCiAgfQogIH0sIGJ5ID0gLihpZC5pLCBpZC5qKV0KcmVjIDwtIGJhdHMuZGl2W2lkLmkgIT0gaWQual0Kc2V0bmFtZXMocmVjLCBuYW1lcyhyZWMpLCBzYXBwbHkobmFtZXMocmVjKSwgZnVuY3Rpb24oc3RyKSB7CiAgaWYgKGdyZXBsKCJcXC5pIiwgc3RyKSkgc3ViKCJcXC5pIiwgIlxcLmoiLCBzdHIpCiAgZWxzZSBpZiAoZ3JlcGwoIlxcLmoiLCBzdHIpKSBzdWIoIlxcLmoiLCAiXFwuaSIsIHN0cikKICBlbHNlIHN0cgp9KSkKYmF0cy5kaXYgPC0gcmJpbmQoYmF0cy5kaXYsIHJlYykKYmF0cy5kaXZbLCBkaXN0YW5jZSA6PSBzcXJ0KGpzZCldCmJhdHMuZGl2WywgIjo9IiAobW9udGguaSA9IGFzLm51bWVyaWMobW9udGguaSksIAogICAgICAgICAgICAgICAgIG1vbnRoLmogPSBhcy5udW1lcmljKG1vbnRoLmopKV0KYmF0cy5kaXZbLCBkZWx0YSA6PSBtb250aC5qIC0gbW9udGguaV0KYGBgCmBgYHtyIGJhdHMtanNkLW1kc30KdmVydGljZXMgPC0gdW5pcXVlKGJhdHNbLCAuKGlkLCBtb250aCwgY2FsLm1vbnRoLCBkZXB0aCldKQplZGdlcyA8LSBiYXRzLmRpdltkZWx0YSA9PSAxLCAuKGlkLmksIGlkLmosIGRlcHRoID0gYXMubnVtZXJpYyhkZXB0aCkpXQpncmFwaCA8LSBncmFwaF9mcm9tX2RhdGFfZnJhbWUoZWRnZXMsIGRpcmVjdGVkID0gRkFMU0UsIHZlcnRpY2VzKQpiYXRzLmRlcHRocyA8LSB1bmlxdWUoYmF0cyRkZXB0aCkKYmF0cy5kZXB0aHMgPC0gYmF0cy5kZXB0aHNbb3JkZXIoYXMubnVtZXJpYyhiYXRzLmRlcHRocykpXQpuYW1lcyhiYXRzLmRlcHRocykgPC0gYmF0cy5kZXB0aHMKYmF0cy5kbXMgPC0gbGFwcGx5KGJhdHMuZGVwdGhzLCBmdW5jdGlvbihkZSkgewogIGQgPC0gYmF0cy5kaXZbZGVwdGggPT0gZGVdCiAgTWFrZURpc3RNYXRyaXgoZCwgImlkLmkiLCAiaWQuaiIpCn0pCmZpdHMgPC0gbGFwcGx5KGJhdHMuZG1zLCBmdW5jdGlvbihkbSkgewogIENvb3JkQ01EUyhkbSkKfSkKeGZvcm1zIDwtIGxhcHBseShmaXRzLCBmdW5jdGlvbih4KSB7CiAgeCRwb2ludHMKfSkgJT4lIHJiaW5kbGlzdCh1c2UubmFtZXMgPSBUUlVFLCBpZGNvbCA9ICJkZXB0aCIpCmVpZ3JhbmtzIDwtIGxhcHBseShmaXRzLCBmdW5jdGlvbih4KSB7CiAgeCRlaWdyYW5rCn0pICU+JSByYmluZGxpc3QodXNlLm5hbWVzID0gVFJVRSwgaWRjb2wgPSAiZGVwdGgiKQplaWdyYW5rc1ssIGRlcHRoIDo9IGZhY3RvcihkZXB0aCwgbGV2ZWxzID0gYmF0cy5kZXB0aHMpXQpgYGAKYGBge3IgYmF0cy1wYXRoLXBsb3RzLGZpZy53aWR0aD03LGZpZy5oZWlnaHQ9OX0Kc2V0a2V5KHhmb3Jtcywgc2FtcGxlKQpsbyA8LSBjcmVhdGVfbGF5b3V0KGdyYXBoLCAibWFudWFsIiwgbm9kZS5wb3NpdGlvbnMgPSB4Zm9ybXNbVihncmFwaCkkbmFtZV0pCm1icmVha3MgPC0gYygxLCAzLCA2LCA5LCAxMikgIyBKYW4sIHBsdXMgbW9udGhzIG9mIHNvbHN0aWNlcyArIGVxdWlub3hlcwpnZ3JhcGgobG8pICsKICBnZW9tX2VkZ2VfbGluayhhcnJvdyA9IGFycm93KHR5cGUgPSAiY2xvc2VkIiwgbGVuZ3RoID0gdW5pdCgzLCAicG9pbnRzIikpLAogICAgICAgICAgICAgICAgIGVuZF9jYXAgPSBzcXVhcmUobGVuZ3RoID0gMywgdW5pdCA9ICJwb2ludHMiKSwKICAgICAgICAgICAgICAgICBlZGdlX3dpZHRoID0gMC4yKSArCiAgZ2VvbV9ub2RlX3BvaW50KGFlcyhjb2xvciA9IGNhbC5tb250aCksIHNpemUgPSAwLjUpICsKICBzY2FsZV9jb2xvcl9ncmFkaWVudG4odmFsdWVzID0gc2NhbGVzOjpyZXNjYWxlKG1icmVha3MpLAogICAgICAgICAgICAgICAgICAgICAgICBjb2xvcnMgPSBjKCJibHVlIiwgImdyZWVuNCIsICJ5ZWxsb3ciLCAib3JhbmdlIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAiYmx1ZSIpCiAgICAgICAgICAgICAgICAgICAgICAgICkgKwogIGZhY2V0X3dyYXAofiBkZXB0aCwgbmNvbCA9IDMpICsKICB0aGVtZV9ncmFwaChiYXNlX2ZhbWlseSA9ICJIZWx2ZXRpY2EiKSArCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkKYGBgCgpUaGlzIGFsc28gc2hvd3MgdGhhdCBzZWFzb25hbCBjeWNsaW5nIGlzIG1vcmUgcmVwcm9kdWNpYmxlIGF0IHNvbWUgZGVwdGhzLgpGb3IgZGVwdGhzIHNoYWxsb3dlciB0aGFuIDEwMCwgdGhlcmUgc2VlbXMgdG8gYmUgYSByZXByb2R1Y2libGUgcGF0aCwgYW5kIHRoZSBjb21wb3NpdGlvbiBzZWVtcyB0byBjaGFuZ2UgbW9yZSBncmFkdWFsbHksIGFzIGNhbiBiZSBzZWVuIGluIHRoZSBjbG9zZSBzcGFjaW5nIG9mIG1vc3QgY29uc2VjdXRpdmUgdGltZXBvaW50cy4KRm9yIGRlcHRocyAxMjAtMTYwLCB0aGVyZSBhcmUgYWxzbyByZXByb2R1Y2libGUgcGF0aHMsIGhvd2V2ZXIsIHRoZXJlIGFyZSAzIGNsdXN0ZXJzIG9mIHRpbWUgcG9pbnRzIChzZWVtaW5nbHkgcmVwcmVzZW50aW5nIHNwcmluZywgc3VtbWVyL2Vhcmx5IGZhbGwsIGFuZCBsYXRlIGZhbGwvd2ludGVyKSB3aXRoIGxhcmdlIGdhcHMgYmV0d2VlbiB0aGVtLCBhbmQgdGhlIGxvbmcgbGVhcHMgYmV0d2VlbiBjbHVzdGVycyBzdWdnZXN0cyB0aGUgc2Vhc29uYWwgY29tcG9zaXRpb25hbCB0cmFuc2l0aW9ucyBhcmUgbW9yZSBkcmFzdGljLgpGaW5hbGx5LCBkZXB0aHMgMTgwLTIwMCBhcHBlYXIgbW9yZSByYW5kb20uCgpFaWdlbnZhbHVlcyBvZiBNRFMgc2hvdyB0aGF0IHRoaXMgdHJhbnNmb3JtYXRpb24gY2FwdHVyZXMgbW9zdCBvZiB0aGUgaW5mb3JtYXRpb246CmBgYHtyLGJhdHMtanNkLWVpZ30KZ2dwbG90KGVpZ3JhbmtzLCBhZXMoeCA9IHJhbmssIHkgPSB2YWx1ZSBeMikpICsKICBnZW9tX3BvaW50KCkgKwogIHNjYWxlX3hfbG9nMTAoKSArCiAgZmFjZXRfd3JhcCh+IGRlcHRoLCBzY2FsZXMgPSAiZnJlZV95IikKYGBgCgpIZWF0bWFwcGluZyB0aGUgSlNEcyBzaG93cyBvY2N1cGFuY3kgb2Ygc3RhYmxlIHN0YXRlcyBhcyBkYXJrIHNxdWFyZXMgb2YgaGlnaCB0ZW1wb3JhbCBzaW1pbGFyaXR5IGFsb25nIHRoZSBkaWFnb25hbC4KUmVjdXJyZW5jZSBvZiBzdGFibGUgc3RhdGVzIHNob3cgYXMgZGFyayBvZmYtZGlhZ29uYWwgcmVjdGFuZ2xlcy4KSXQgaXMgY2xlYXIgdGhlIHRpbWUgc2NhbGVzIG9mIHN0YWJpbGl0eSAoc2l6ZXMgb2Ygb24tZGlhZ29uYWwgZGFyayBzcXVhcmVzKSBhcmUgZGlmZmVyZW50IGZvciBkZXB0aHMgMS00MCBhbmQgMTAwLTE2MC4KNjAtODAgc2VlbSB0byBiZSBhIGh5YnJpZCBvZiB0aGUgdHdvIHJlZ2ltZXMsIGFuZCAxODAtMjAwIHNlZW0gdG8gZ28gdG93YXJkIHJhbmRvbW5lc3MuCmBgYHtyIGJhdHMtdGlsZSxmaWcuYXNwPTEuNX0KYmF0cy5kaXZbLCBkZXB0aCA6PSBhcy5udW1lcmljKGRlcHRoKV0KZ2dwbG90KGJhdHMuZGl2LCBhZXMoeCA9IG1vbnRoLmksIHkgPSBtb250aC5qKSkgKwogIGdlb21fdGlsZShhZXMoZmlsbCA9IGpzZCkpICsgCiAgZmFjZXRfd3JhcCh+IGRlcHRoLCBuY29sID0gMykgKyAKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKQpgYGAKCkRhdmlkLXN0eWxlLCBKU0QtYmFzZWQgJ2F1dG9jb3JyZWxhdGlvbi4nClRoZSBwZXJpb2RpY2l0eSBvZiBtYW55IG9mIHRoZSBhdXRvY29ycmVsYXRpb24gZnVuY3Rpb25zIHNob3dzIHN0cm9uZyBwZXJpb2RpYyBkeW5hbWljcyBhdCBhIHNpbmdsZSB0aW1lIHNjYWxlLgpgYGB7ciBiYXRzLWF1dG9jb3JyLGZpZy5hc3A9MX0KZ2dwbG90KGJhdHMuZGl2W2RlbHRhID4gMF0sIGFlcyh4ID0gZGVsdGEsIHkgPSBqc2QpKSArCiAgZ2VvbV9wb2ludChzaXplID0gMC4yKSArCiAgZ2VvbV9zbW9vdGgoKSArCiAgZmFjZXRfd3JhcCh+IGRlcHRoLCBuY29sID0gMykgCmBgYAoKIyMjIERlbmRyb2dyYW0KCkZvciB0aGlzIGRhdGFzZXQsIHRoZSBwYXRoIHBsb3RzIG1pZ2h0IGFjdHVhbGx5IG1ha2UgdGhlIHBvaW50IG1vcmUgY2xlYXJseS9jb252aW5jaW5nbHkgdGhhbiB0aGUgZGVuZHJvZ3JhbSB3aGVlbHMuCgpgYGB7ciBiYXRzLWRlbmRyby1wbG90cywgZmlnLndpZHRoPTcsZmlnLmhlaWdodD0xMH0KIyBjbHVzdGVyaW5nCmJhdHMuaW5mb1ssIG1vbnRoIDo9IGFzLmNoYXJhY3Rlcihtb250aCldCnNldGtleShiYXRzLmluZm8sIG1vbnRoKQpiYXRzLmRlbmRyb3MgPC0gbGFwcGx5KGJhdHMuZG1zLCBmdW5jdGlvbihkbSkgewogIGhjIDwtIGhjbHVzdChkaXN0KGRtKSkKICBkZW5kcm8gPC0gYXMuZGVuZHJvZ3JhbShoYykKICBkZW5kcm8gPC0gZGVuZHJhcHBseShkZW5kcm8sIGZ1bmN0aW9uKGQpIHsKICAgIGlmIChpcy5sZWFmKGQpKSB7CiAgICAgIGxhYmwgPC0gYXR0cihkLCAibGFiZWwiKQogICAgICBtbyA8LSBzdHJzcGxpdChsYWJsLCAiXyIpW1sxXV1bMV0KICAgICAgY2FsLm1vbnRoIDwtIHVuaXF1ZShiYXRzLmluZm9bbW8sIGNhbC5tb250aF0pICMgZm9yIG11bHRpcGxlIHBhc3Nlcy9tbwogICAgICB5ZWFyIDwtIHVuaXF1ZShiYXRzLmluZm9bbW8sIHllYXJdKSAjIGZvciBtdWx0aXBsZSBwYXNzZXMvbW8KICAgICAgYXR0cihkLCAibm9kZVBhciIpIDwtIGxpc3QobW9udGggPSBhcy5udW1lcmljKG1vKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY2FsLm1vbnRoID0gY2FsLm1vbnRoLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB5ZWFyID0geWVhcgogICAgICApCiAgICB9CiAgICBkCiAgfSkKICBkZW5kcm8gPC0gdHJlZV9hcHBseShkZW5kcm8sIGZ1bmN0aW9uKG5vZGUsIGNoaWxkcmVuLCBkZXB0aCwgdHJlZSkgewogICAgaWYoIWlzLmxlYWYobm9kZSkpIHsKICAgICAgY2hpbGQubW9udGhzIDwtIHNhcHBseShjaGlsZHJlbiwgZnVuY3Rpb24obikgewogICAgICAgIGF0dHIobiwgIm5vZGVQYXIiKSRjYWwubW9udGgKICAgICAgfSkKICAgICAgY2FsLm1vbnRoIDwtIG1lYW4oY2hpbGQubW9udGhzKQogICAgICBhdHRyKG5vZGUsICJub2RlUGFyIikgPC0gYXBwZW5kKGF0dHIobm9kZSwgIm5vZGVQYXIiKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsaXN0KGNhbC5tb250aCA9IGNhbC5tb250aCkpCiAgICB9CiAgICBub2RlCiAgfSwgZGlyZWN0aW9uID0gInVwIikKICBkZW5kcm8KfSkKYmF0cy5sb3MgPC0gbGFwcGx5KGJhdHMuZGVuZHJvcywgZnVuY3Rpb24oZGVuZHJvKSB7CiAgY3JlYXRlX2xheW91dChkZW5kcm8sICJkZW5kcm9ncmFtIiwgY2lyY3VsYXIgPSBUUlVFKQp9KQpiYXRzLmRlbmRyb2dyYXBocyA8LSBsYXBwbHkoYmF0cy5sb3MsIGZ1bmN0aW9uKGxheW91dCkgewogIGdncmFwaChsYXlvdXQpICsKICAgIGdlb21fZWRnZV9lbGJvdygpICsKICAgICMgZ2VvbV9lZGdlX2VsYm93KGFlcyhjb2xvciA9IG5vZGUyLmNhbC5tb250aCkpICsKICAgICMgc2NhbGVfZWRnZV9jb2xvcl9ncmFkaWVudG4odmFsdWVzID0gc2NhbGVzOjpyZXNjYWxlKG1icmVha3MpLAogICAgIyAgICAgICAgICAgICAgICAgICAgICAgY29sb3JzID0gYygiYmx1ZSIsICJncmVlbjQiLCAieWVsbG93IiwgIm9yYW5nZSIsCiAgICAjICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICJibHVlIikpICsKICAgIHRoZW1lX2dyYXBoKGJhc2VfZmFtaWx5ID0gIkhlbHZldGljYSIpICsKICAgIGdlb21fbm9kZV9wb2ludChhZXMoZmlsdGVyID0gbGVhZiwgY29sb3IgPSBjYWwubW9udGgsIAogICAgICAgICAgICAgICAgICAgICAgICBzaGFwZSA9IGFzLmNoYXJhY3Rlcih5ZWFyKSksCiAgICAgICAgICAgICAgICAgICAgc2l6ZSA9IDEpICsKICAgIHNjYWxlX2NvbG9yX2dyYWRpZW50bih2YWx1ZXMgPSBzY2FsZXM6OnJlc2NhbGUobWJyZWFrcyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgY29sb3JzID0gYygiYmx1ZSIsICJncmVlbjQiLCAieWVsbG93IiwgIm9yYW5nZSIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAiYmx1ZSIpKSArCiAgICB0aGVtZV9ncmFwaChiYXNlX2ZhbWlseSA9ICJIZWx2ZXRpY2EiKSArCiAgICB0aGVtZShhc3BlY3QucmF0aW8gPSAxLCBsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCn0pCnBsb3RfZ3JpZChwbG90bGlzdCA9IGJhdHMuZGVuZHJvZ3JhcGhzLCBsYWJlbHMgPSBuYW1lcyhiYXRzLmRlbmRyb2dyYXBocyksCiAgICAgICAgICBuY29sID0gMykKYGBgCgojIyBDb2Fyc2UtZ3JhaW5pbmcgc3RhdGVzCkxldCB0aGUgZGVwdGggPSAxIG5vZGUgSUQgYmUgdGhlIHN0YXRlIGxhYmVsIG9mIGVhY2ggdGltZSBwb2ludC4KQWdhaW4sIHRoaXMgbWV0aG9kIGRvZXNuJ3Qgc2VlbSB0byBnaXZlIG11Y2ggZXh0cmEgaW5mb3JtYXRpb24gZm9yIHRoaXMgZGF0YXNldC4KUGVyaGFwcyB0aGVyZSdzIHNvbWUgb3RoZXIgd2F5IHRvIGRvIHRoaXMuCmBgYHtyIGJhdHMtc3RhdGVzLWNvYXJzZWdyYWlufQojIGNyZWF0ZSBhIHVuaXF1ZSBJRCBmb3IgZWFjaCBzdGF0ZSBhdCBkZXB0aCA9IDIgYW5kIHByb3BhZ2F0ZSBkb3duIApiYXRzLmRlbmRyb3MgPC0gbGFwcGx5KGJhdHMuZGVuZHJvcywgZnVuY3Rpb24oZGVuZHJvLCB0aHJlc2ggPSAyKSB7CiAgIyBwcm9wYWdhdGUgdXAKICBkZW5kcm8gPC0gdHJlZV9hcHBseShkZW5kcm8sIGZ1bmN0aW9uKG5vZGUsIGNoaWxkcmVuLCBkZXB0aCwgdHJlZSwgdGggPSB0aHJlc2gpIHsKICAgIGlmIChpcy5sZWFmKG5vZGUpKSB7CiAgICAgIG1vIDwtIHN0cnNwbGl0KCJfIiwgYXR0cihub2RlLCAibGFiZWwiKSlbWzFdXVtbMV1dCiAgICAgIHN0YXRlIDwtIGF0dHIobm9kZSwgImxhYmVsIikKICAgIH0gZWxzZSB7CiAgICAgIGlmIChkZXB0aCA+PSB0aCkgewogICAgICAgIGNoaWxkLnN0YXRlcyA8LSBzYXBwbHkoY2hpbGRyZW4sIGZ1bmN0aW9uKGQpIGF0dHIoZCwgIm5vZGVQYXIiKSRzdGF0ZSkKICAgICAgICAjIHRha2UgdGhlIGZpcnN0IGNoaWxkIHN0YXRlIGFzIGJyYW5jaCBzdGF0ZQogICAgICAgIHN0YXRlIDwtIGNoaWxkLnN0YXRlc1tbMV1dCiAgICAgIH0gZWxzZSB7CiAgICAgICAgc3RhdGUgPC0gTkEKICAgICAgfQogICAgfQogICAgaWYgKGlzLm51bGwgKHN0YXRlKSkgYnJvd3NlcigpCiAgICBhdHRyKG5vZGUsICJub2RlUGFyIikgPC0gYXBwZW5kKGF0dHIobm9kZSwgIm5vZGVQYXIiKSwgbGlzdChzdGF0ZSA9IHN0YXRlKSkKICAgIG5vZGUKICB9LCBkaXJlY3Rpb24gPSAidXAiKQogICMgcHJvcGFnYXRlIGRvd24KICBkZW5kcm8gPC0gdHJlZV9hcHBseShkZW5kcm8sIGZ1bmN0aW9uKG5vZGUsIHBhcmVudCwgZGVwdGgsIHRyZWUsIHRoID0gdGhyZXNoKSB7CiAgICBpZiAoZGVwdGggPiB0aCkgewogICAgICBwYXJzdGF0ZSA8LSBhdHRyKHBhcmVudCwgIm5vZGVQYXIiKSRzdGF0ZQogICAgICBhdHRyKG5vZGUsICJub2RlUGFyIikkc3RhdGUgPC0gcGFyc3RhdGUKICAgIH0KICAgIG5vZGUKICB9KQogIGRlbmRybwp9KQpgYGAKYGBge3IgYmF0cy1zdGF0ZXMtY29hcnNlZ3JhaW4tcHJvYmFiaWxpdHksZmlnLndpZHRoPTcsZmlnLmhlaWdodD05fQpwbC5iYXRzLnN0YXRlcyA8LSBsYXBwbHkoYmF0cy5kZW5kcm9zLCBmdW5jdGlvbihkZW5kcm8pIHsKICBnZ3JhcGgoZGVuZHJvLCAiZGVuZHJvZ3JhbSIsIGNpcmN1bGFyID0gVFJVRSkgKwogIGdlb21fZWRnZV9lbGJvdyhhZXMoY29sb3IgPSBub2RlMi5zdGF0ZSkpICsKICBnZW9tX25vZGVfcG9pbnQoYWVzKGZpbHRlciA9IGxlYWYsIAogICAgICAgICAgICAgICAgICAgICAgY29sb3IgPSBjYWwubW9udGgpLAogICAgICAgICAgICAgICAgICBzaXplID0gMQogICAgICAgICAgICAgICAgICApKwogIHRoZW1lX2dyYXBoKGJhc2VfZmFtaWx5ID0gIkhlbHZldGljYSIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxLCBsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpICsgCiAgc2NhbGVfY29sb3JfZ3JhZGllbnRuKHZhbHVlcyA9IHNjYWxlczo6cmVzY2FsZShtYnJlYWtzKSwKICAgICAgICAgICAgICAgICAgICAgICAgY29sb3JzID0gYygiYmx1ZSIsICJncmVlbjQiLCAieWVsbG93IiwgIm9yYW5nZSIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgImJsdWUiKSkgKwogIGd1aWRlcyhzaGFwZSA9IGd1aWRlX2xlZ2VuZChuY29sID0gMiksCiAgICAgICAgIGVkZ2VfY29sb3VyID0gZ3VpZGVfbGVnZW5kKG5jb2wgPSAyKSkKfSkKcGxvdF9ncmlkKHBsb3RsaXN0ID0gcGwuYmF0cy5zdGF0ZXMsIG5jb2wgPSAzLCBsYWJlbHMgPSBuYW1lcyhwbC5iYXRzLnN0YXRlcykpCmJhdHMuc2FtcHMyc3RhdGVzIDwtIGxhcHBseShiYXRzLmRlbmRyb3MsIGZ1bmN0aW9uKGRlbmRybykgewogIGdyYWYgPC0gZGVuX3RvX2lncmFwaChkZW5kcm8pCiAgaXNsZiA8LSBWKGdyYWYpJGxlYWYKICB5ciA8LSBWKGdyYWYpJHllYXJbaXNsZl0KICBtbyA8LSBWKGdyYWYpJG1vbnRoW2lzbGZdCiAgY20gPC0gVihncmFmKSRjYWwubW9udGhbaXNsZl0KICBzdCA8LSBWKGdyYWYpJHN0YXRlW2lzbGZdCiAgZGF0YS50YWJsZShtb250aCA9IG1vLCB5ZWFyID0geXIsIGNhbC5tb250aCA9IGNtLCBzdGF0ZSA9IHN0KQp9KSAlPiUgcmJpbmRsaXN0KGlkY29sID0gImRlcHRoIikKZ2dwbG90KGJhdHMuc2FtcHMyc3RhdGVzLCBhZXMoeCA9IGNhbC5tb250aCwgeSA9IHN0YXRlLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29sb3IgPSBhcy5jaGFyYWN0ZXIoeWVhcikpKSArCiAgZ2VvbV9saW5lKGFlcyhncm91cCA9IHllYXIpKSArCiAgIyBnZW9tX2ppdHRlcih3aWR0aCA9IDAsIGhlaWdodCA9IDAuMykgKwogIGxhYnMoY29sb3IgPSAieWVhciIpICsKICAjIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJib3R0b20iKSArCiAgZmFjZXRfd3JhcCh+IGRlcHRoLCBzY2FsZXMgPSAiZnJlZV95IiwgbmNvbCA9IDIpCmBgYAoKCiMgTmFoYW50CgpUaGVyZSBhcmUgdG9vIG1hbnkgT1RVcy4KVGhleSBzaG91bGQgcHJvYmFibHkgYmUgYWdncmVnYXRlZCBzb21laG93LgpIZXJlIHdlIGFnZ3JlZ2F0ZSBhbGwgcmVhZHMgdGhhdCBtYXAgdG8gdGhlIHNhbWUgcGh5bHVtLCB3aGljaCByZXN1bHRzIGluIGEgbWFuYWdlYWJsZSBudW1iZXIgb2YgdmFyaWFibGVzLgpCdXQgb25lIGNvdWxkIGp1c3QgYXMgd2VsbCBhZ2dyZWdhdGUgYXQgYW55IG90aGVyIHRheG9ub21pYyBsZXZlbCBvciBub3QgYXQgYWxsLgpgYGB7cn0KbmFoYW50LmJhYyA8LSBmcmVhZChwYXN0ZTAoZGF0YS5kaXIsICJCYWN0Tm9ybS50eHQiKSwgaGVhZGVyID0gVFJVRSkKbmFoYW50LmJhYyA8LSBtZWx0KG5haGFudC5iYWMsIGlkLnZhcnMgPSBjKCJPVFUiLCAiQ29uc2Vuc3VzTGluZWFnZSIpLCAKICAgICAgICAgICAgICAgICAgIHZhcmlhYmxlLm5hbWUgPSAiZGF5IikKbmFoYW50LmJhYyA8LSBuYWhhbnQuYmFjWywgZGF5IDo9IGFzLm51bWVyaWMoYXMuY2hhcmFjdGVyKGRheSkpXQpuYWhhbnQuYmFjIDwtIG5haGFudC5iYWNbLCB2YWx1ZSA6PSBhcy5udW1lcmljKHZhbHVlKV0KIyBtZXJnZSBPVFUgY291bnRzIGJ5IGNvbnNlbnN1cyBsaW5lYWdlCm5haGFudC5iYWMgPC0gbmFoYW50LmJhY1ssIC4oZnJlcSA9IHN1bSh2YWx1ZSkpLCBieSA9IC4oQ29uc2Vuc3VzTGluZWFnZSwgZGF5KV0KIyBwYXJzZSBsaW5lYWdlCiMgbm90aGluZyBpcyBtYXBwZWQgdG8gc3BlY2llcyByZXNvbHV0aW9uCm5haGFudC5iYWMgPC0gbmFoYW50LmJhY1ssIENvbnNlbnN1c0xpbmVhZ2UgOj0gZ3N1YigiOyIsICIiLCBDb25zZW5zdXNMaW5lYWdlKV0KbmFoYW50LmJhYyA8LSBuYWhhbnQuYmFjWywgYygiZm9vIiwgImtpbmdkb20iLCAicGh5bHVtIiwgImNsYXNzIiwgIm9yZGVyIiwgImZhbWlseSIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgImdlbnVzIikgOj0gdHN0cnNwbGl0KENvbnNlbnN1c0xpbmVhZ2UsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAiW1s6YWxwaGE6XV1fXyIpXQpuYWhhbnQuYmFjIDwtIG5haGFudC5iYWNbLCBmb28gOj0gTlVMTF0KIyB0aGVyZSBhcmUgd2F5IHRvbyBtYW55IGNsYXNzZXMgYW5kIGZpbmVyLCBwbG90IHRpbWUgc2VyaWVzIG9mIHBoeWxhCnBoeWxhIDwtIG5haGFudC5iYWNba2luZ2RvbSAhPSAiIiAmIHBoeWx1bSAhPSAiIiwgLihmcmVxID0gc3VtKGZyZXEpKSwgCiAgICAgICAgICAgYnkgPSAuKGRheSwgcGh5bHVtKV0gCmBgYApgYGB7ciBuYWhhbnQtdHMsIGZpZy5hc3A9MX0KcGh5bGEgJT4lIAogIGdyb3VwX2J5KHBoeWx1bSkgJT4lIAogIG11dGF0ZShmcmVxID0gc2NhbGVzOjpyZXNjYWxlKGZyZXEpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gYXMubnVtZXJpYyhkYXkpLCB5ID0gZnJlcSkpICsKICB0aGVtZShzdHJpcC50ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMCksCiAgICAgICAgYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA5MCwgdmp1c3QgPSAwLjUsIGhqdXN0ID0gMSkKICAgICAgICApICsKICBzY2FsZV95X2NvbnRpbnVvdXMoYnJlYWtzID0gYygwLCAwLjUsIDEpKSArCiAgZ2VvbV9saW5lKGFlcyhncm91cCA9IHBoeWx1bSkpICsKICBmYWNldF93cmFwKH4gcGh5bHVtLCBuY29sID0gNCkgKwogIGxhYnMoeSA9ICJmcmVxdWVuY3kgKG5vcm1hbGl6ZWQpIikKYGBgCgpXZSBjYW4gbG9vayBhdCB0aGUgc3BlY3RyYWwgZGVuc2l0eSBvZiB0aGUgcGh5bGEgdGltZSBzZXJpZXMuClBoeWxhIHdpdGggcGVha3MgaW4gdGhlIGxvdyBmcmVxdWVuY2llcyBleGhpYml0IHNsb3cgZmx1Y3R1YXRpb25zLgpJdCBzZWVtcyB0aGVyZSByZWFsbHkgYXJlIHNsb3cgYW5kIGJyb2FkLXNwZWN0cnVtIHRheGEgYXQgdGhpcyBsZXZlbC4KYGBge3IgbmFoYW50LXBoeWxhLXNwZWN0cmF9CnBoeWxhLnNwZWMgPC0gcGh5bGEgJT4lCiAgZGNhc3QoZGF5IH4gcGh5bHVtLCB2YWx1ZS52YXIgPSAiZnJlcSIpICU+JSAKICBzZWxlY3QoLWRheSkgJT4lIAogIHN0YXRzOjpzcGVjdHJ1bShwbG90ID0gRkFMU0UpCnBoeWxhLnNwZWMgPC0gZGF0YS50YWJsZShjYmluZChwaHlsYS5zcGVjJGZyZXEsIHBoeWxhLnNwZWMkc3BlYykpICU+JSAKICBzZXRuYW1lcyhjKCJmcmVxIiwgcGh5bGEuc3BlYyRzbmFtZXMpKSAlPiUgCiAgbWVsdChpZC52YXJzID0gImZyZXEiLCB2YXJpYWJsZS5uYW1lID0gInBoeWx1bSIpCnBoeWxhLnNwZWMgJT4lIAogIGdyb3VwX2J5KHBoeWx1bSkgJT4lIAogIG11dGF0ZSh2YWx1ZSA9IHZhbHVlIC8gc3VtKHZhbHVlKSkgJT4lIAogIGdncGxvdChhZXMoeCA9IGZyZXEsIHkgPSBwaHlsdW0pKSArCiAgbGFicyh4ID0gImZyZXF1ZW5jeSAoMS9kYXkpIikgKwogIGdlb21fdGlsZShhZXMoZmlsbCA9IHZhbHVlKSkgCmBgYAoKIyBSIHRoZXJlIHN0YXRlej8KCkFyZSB0aGVyZSBxdWFsaXRhdGl2ZSBjb2Fyc2UtZ3JhaW5hYmxlIGNvbXBvc2l0aW9uYWwgc3RhdGVzIGluIHRoZSBOYWhhbnQgZGF0YT8KYGBge3IgbmFoYW50LWNvbXBvc2l0aW9uLWNsdXN0ZXJpbmd9CnBoeWxhWywgZGF5IDo9IGFzLmNoYXJhY3RlcihkYXkpXQpkYXlzIDwtIHVuaXF1ZShwaHlsYVssIGRheV0pCmRheS5kaXYgPC0gZGF0YS50YWJsZShleHBhbmQuZ3JpZChkYXkuaSA9IGRheXMsIGRheS5qID0gZGF5cykpCmRheS5kaXZbLCAiOj0iIChkYXkuaSA9IGFzLmNoYXJhY3RlcihkYXkuaSksIAogICAgICAgICAgICAgICAgICAgICAgICAgICBkYXkuaiA9IGFzLmNoYXJhY3RlcihkYXkuaikpXQpzZXRrZXkocGh5bGEsIGRheSkKZGF5LmRpdlssIGpzZCA6PSB7CiAgaWYgKGRheS5pID09IGRheS5qKSB7CiAgICAwCiAgfSBlbHNlIHsKICAgIHNkIDwtIHBoeWxhW2MoZGF5LmksIGRheS5qKV0KICAgIHNkIDwtIGRjYXN0KHNkLCBwaHlsdW0gfiBkYXksIHZhbHVlLnZhciA9ICJmcmVxIikKICAgIG0gPC0gYXMubWF0cml4KHNkWywgMjozXSkKICAgIGQgPC0gZ2VuSlNEKG0pCiAgICBkCiAgfQp9LCBieSA9IC4oZGF5LmksIGRheS5qKV0KZGF5LmRpdlssIGRpc3RhbmNlIDo9IHNxcnQoanNkKV0KYGBgCgpMYXlvdXQgdGhlIHNhbXBsZXMgYnkgSmVuc2VuLVNoYW5ub24gZGlzdGFuY2UgdXNpbmcgYG1kc2AgYWxnb3JpdGhtLgpDb2xvciBieSBkYXkgc28gYXMgdG8gc2VlIHRlbXBvcmFsIHByb2dyZXNzaW9uLgpIaWVyYXJjaGljYWxseSBjbHVzdGVyIGJ5IEpTIGRpc3RhbmNlLgoKYGBge3IgbmFoYW50LWNvbXBvc2l0aW9uLWNsdXN0ZXJpbmctcGxvdCwgZmlnLmhlaWdodD03LCBmaWcud2lkdGg9N30KZWRnZXMgPC0gY2JpbmQoZGF5c1stbGVuZ3RoKGRheXMpXSwgZGF5c1stMV0pCmdyYXBoIDwtIGdyYXBoX2Zyb21fZGF0YV9mcmFtZShlZGdlcywgZGlyZWN0ZWQgPSBGQUxTRSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZlcnRpY2VzID0gZGF0YS50YWJsZShpZCA9IGRheXMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGF5ID0gYXMubnVtZXJpYyhkYXlzKSkpCmRtIDwtIE1ha2VEaXN0TWF0cml4KGRheS5kaXYsICJkYXkuaSIsICJkYXkuaiIpCmZpdCA8LSBDb29yZENNRFMoZG0pCnhmb3JtIDwtIGZpdCRwb2ludHMKIyBvcmRlcgpzZXRrZXkoeGZvcm0sIHNhbXBsZSkKeGZvcm0gPC0geGZvcm1bVihncmFwaCkkbmFtZV0KbGF5b3V0IDwtIGNyZWF0ZV9sYXlvdXQoZ3JhcGgsICJtYW51YWwiLCBub2RlLnBvc2l0aW9ucyA9IHhmb3JtKQpwMSA8LSBnZ3JhcGgobGF5b3V0KSArCiAgZ2VvbV9lZGdlX2xpbmsoYXJyb3cgPSBhcnJvdyh0eXBlID0gImNsb3NlZCIsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbGVuZ3RoID0gdW5pdCg1LCAicG9pbnRzIikpLAogICAgICAgICAgICAgICAgIGVkZ2Vfd2lkdGggPSAwLjIsCiAgICAgICAgICAgICAgICAgZW5kX2NhcCA9IHNxdWFyZShsZW5ndGggPSA1LCB1bml0ID0gInBvaW50cyIpCiAgICAgICAgICAgICAgICAgKSArCiAgZ2VvbV9ub2RlX3BvaW50KGFlcyhjb2xvciA9IGRheSkpICsKICB0aGVtZV9ncmFwaChiYXNlX2ZhbWlseSA9ICJIZWx2ZXRpY2EiKSArCiAgc2NhbGVfY29sb3JfZGlzdGlsbGVyKHBhbGV0dGUgPSAiU3BlY3RyYWwiKSAKIyBjbHVzdGVyaW5nCmhjIDwtIGhjbHVzdChkaXN0KGRtKSkKZGVuZHJvIDwtIGFzLmRlbmRyb2dyYW0oaGMpCmRlbmRybyA8LSBkZW5kcmFwcGx5KGRlbmRybywgZnVuY3Rpb24oZCkgewogIGlmIChpcy5sZWFmKGQpKSB7CiAgICBhdHRyKGQsICJub2RlUGFyIikgPC0gbGlzdChkYXkgPSBhcy5udW1lcmljKGF0dHIoZCwgImxhYmVsIikpKQogIH0KICBkCn0pCnAyIDwtIGdncmFwaChkZW5kcm8sICJkZW5kcm9ncmFtIikgKwogIGdlb21fZWRnZV9lbGJvdygpICsKICAjIGdlb21fbm9kZV90ZXh0KGFlcyhmaWx0ZXIgPSBsZWFmLCBjb2xvciA9IGRheSwgbGFiZWwgPSBkYXkpLCBhbmdsZSA9IDkwLCBzaXplID0gMikgKwogIGdlb21fbm9kZV9wb2ludChhZXMoZmlsdGVyID0gbGVhZiwgY29sb3IgPSBkYXkpKSArCiAgc2NhbGVfY29sb3JfZGlzdGlsbGVyKHBhbGV0dGUgPSAiU3BlY3RyYWwiKSArCiAgdGhlbWVfZ3JhcGgoYmFzZV9mYW1pbHkgPSAiSGVsdmV0aWNhIikgIysKICAjIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEpCnBsb3RfZ3JpZChwMSwgcDIsIG5yb3cgPSAyLCBhbGlnbiA9ICJodiIsIGxhYmVscyA9IGMoIkEiLCAiQiIpKQpgYGAKVGhlc2UgZGF0YSBzaG93IGEgY2xlYXIgdHJhbnNpdGlvbiBiZXR3ZWVuIHN0YWJsZSBzdGF0ZXMgYXJvdW5kIGRheSAyNDAuClRoZXNlIHR3byBzdGF0ZXMgZm9ybSB0aGUgdHdvIG1ham9yIGJyYW5jaGVzIGF0IHRoZSBsb3dlc3QgbGV2ZWwgb2YgdGhlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nLgoKVGhlIGVpZ2VudmFsdWVzIG9mIHRoZSBNRFMgdHJhbnNmb3JtIHNob3cgdGhhdCBpbmZvcm1hdGlvbiBpcyB3ZWxsIHByZXNlcnZlZDoKYGBge3IgYmF0cy1tZHMtZWlnZW59CmdncGxvdChmaXQkZWlncmFuaywgYWVzKHggPSByYW5rLCB5ID0gdmFsdWUgXiAyKSkgKwogIGdlb21fcG9pbnQoKQpgYGAKCgojIyBTdGF0aXN0aWNzIG9mIGR5bmFtaWNzIAoKRGlzdHJpYnV0aW9uIG9mIGRhaWx5IGNvbXBvc2l0aW9uYWwgc3RlcCBzaXplcy4KVGhlIE1heHdlbGwtQm9sdHptYW5uL2xvZ25vcm1hbCBzaGFwZSB0byB0aGUgZGVuc2l0eSBhdCAkXERlbHRhKHQpID0gMSQgCnN1Z2dlc3RzIHRoYXQgdW5kZXIgdGhpcyB0aW1lIHJlc29sdXRpb24gdGhlIGNoYW5nZSBpbiBjb21wb3NpdGlvbiBiZWhhdmVzCmxpa2Ugc29tZSBraW5kIG9mIHJhbmRvbSB3YWxrLCB3aXRoIGEgY2hhcmFjdGVyaXN0aWMgc3RlcCBzaXplIGFuZCByYXJlIGNoYW5nZXMgb2YgbGFyZ2VyIG1hZ25pdHVkZS4KYGBge3IgbmFoYW50LWRheS1kZWx0YXMsIGZpZy53aWR0aD03LGZpZy5oZWlnaHQ9Nn0KZGF5LmRpdiA8LSBkYXkuZGl2WywgZGF5LmRlbHRhIDo9IGFzLm51bWVyaWMoZGF5LmopIC0gYXMubnVtZXJpYyhkYXkuaSldCnAxIDwtIGdncGxvdChkYXkuZGl2W2RheS5kZWx0YSA9PSAxLF0sIGFlcyh4ID0gZGlzdGFuY2UpKSArCiAgc3RhdF9iaW4oYmlucyA9IDMwKSAKcDIgPC0gZ2dwbG90KGRheS5kaXZbZGF5LmRlbHRhID09IDFdLCBhZXMoeCA9IGFzLm51bWVyaWMoZGF5LmkpLCB5ID0gZGlzdGFuY2UpKSArCiAgZ2VvbV9wb2ludCgpICsgCiAgIyBzdGF0X3Ntb290aCgpICsgCiAgbGFicyh4ID0gImRheSBpIikKcGxvdF9ncmlkKHAxLCBwMiwgbnJvdyA9IDIsIGxhYmVscyA9ICJBVVRPIiwgYWxpZ24gPSAiaHYiKQpkYXkuZGl2W2RheS5kZWx0YSA+IDBdICU+JSAKICBtdXRhdGUoZ3JvdXAgPSBhcy5mYWN0b3IoZmxvb3IoZGF5LmRlbHRhIC8gMTApICogMTApLAogICAgICAgICBkZGVsdGEgPSBhcy5mYWN0b3IoZGF5LmRlbHRhICUlIDEwKSkgJT4lIAogIGdncGxvdChhZXMoeCA9IGRpc3RhbmNlKSkgKwogIHN0YXRfYmluKGJpbnMgPSAzMCwgcG9zaXRpb24gPSAiaWRlbnRpdHkiKSArCiAgc2NhbGVfY29sb3JfYnJld2VyKHBhbGV0dGUgPSAiU3BlY3RyYWwiKSArCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA5MCwgdmp1c3QgPSAwLjUsIGhqdXN0ID0gMSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc2l6ZSA9IDcKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICApLAogICAgICAgIGF4aXMudGV4dC55ID0gZWxlbWVudF90ZXh0KHNpemUgPSA2KQogICAgICAgICkgKwogIGZhY2V0X2dyaWQoZ3JvdXAgfiBkZGVsdGEsIHNjYWxlcyA9ICJmcmVlX3kiKQpgYGAKCkNvbXBvc2l0aW9uYWwgZGlzdGFuY2UgYXMgZnVuY3Rpb24gb2YgaW50ZXJ2YWwuClRoaXMgaXMgc29ydCBvZiBhbiBhdXRvY29ycmVsYXRpb24gc3BlY3RydW0uClRoZXJlIGFyZSBubyBwZWFrcyBpbiB0aGlzICdzcGVjdHJ1bScgc3VnZ2VzdGluZyB0aGVyZSBhcmUgbm8gY2hhcmFjdGVyaXN0aWMKdGltZSBzY2FsZXMgb2YgcGVyaW9kaWMgYmVoYXZpb3IuClNpbmNlIHRoZXJlIGlzIG9ubHkgb25lIG1ham9yIHN0YXRlIHRyYW5zaXRpb24gaW4gdGhlc2UgZGF0YSwgaXQgY291bGQgYWxzbyBiZSBpbnRlcnByZXRlZCBhcyB0aGUgcGVyaW9kIG9mIHN0YXRlIHRyYW5zaXRpb25zIGJlaW5nIGxvbmdlciB0aGFuIHRoZSBvYnNlcnZhdGlvbiB0aW1lLCB3aGVuIGludGVycHJldGVkIGFzIHBlcmlvZGljLgpgYGB7ciBuYWhhbnQtc2ltLWludGVydmFsLCBmaWcud2lkdGg9NywgZmlnLmhlaWdodD01fQpiciA8LSBkYXlzW3NlcSgxLCBsZW5ndGgoZGF5cyksIGJ5ID0gNSldCmdncGxvdChkYXkuZGl2LCBhZXMoeCA9IGRheS5pLCB5ID0gZGF5LmopKSArCiAgZ2VvbV90aWxlKGFlcyhmaWxsID0gZGlzdGFuY2UpKSArCiAgc2NhbGVfeF9kaXNjcmV0ZShicmVha3MgPSBicikgKwogIHNjYWxlX3lfZGlzY3JldGUoYnJlYWtzID0gYnIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxLAogICAgICAgIGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gOTAsIHZqdXN0ID0gMC41LCBoanVzdCA9IDEpKQp0bCA8LSBkYXkuZGl2W2RheS5kZWx0YSA+IDAsIC4obW4uZGlzdCA9IG1lYW4oZGlzdGFuY2UpKSwgYnkgPSBkYXkuZGVsdGFdCnAwIDwtIGdncGxvdChkYXkuZGl2W2RheS5kZWx0YSA+IDBdLCBhZXMoeCA9IGRheS5kZWx0YSwgeSA9IGRpc3RhbmNlKSkgCnAxIDwtIHAwICsgZ2VvbV9wb2ludChzaXplID0gMSkgKyAKICAjIHN0YXRfc21vb3RoKGFlcyhsaW5ldHlwZSA9ICJtZWFuIikpICArCiAgZ2VvbV9saW5lKGFlcyh5ID0gbW4uZGlzdCwgbGluZXR5cGUgPSAibWVhbiIpLCB0bCwgY29sb3IgPSAiYmx1ZSIsIHNpemUgPSAyKSArCiAgbGFicyhsaW5ldHlwZSA9ICIiLCB4ID0gImludGVydmFsIChkYXlzKSIpCnAyIDwtIHAwICsgc3RhdF9iaW5fMmQoYmlud2lkdGggPSBjKDEsIDAuMDEpKSArIGxhYnMoeCA9ICJpbnRlcnZhbCAoZGF5cykiKQpwbG90X2dyaWQocDEsIHAyLCBucm93ID0gMiwgYWxpZ24gPSAiaHYiLCBsYWJlbHMgPSAiQVVUTyIpCmBgYAoKIyBIdW1hbgoKIyMgRGF2aWQgZXQgYWwKYGBge3IsbWVzc2FnZT1GQUxTRX0KZGF2aWQgPC0gZnJlYWQocGFzdGUwKGRhdGEuZGlyLCAiZGF2aWQvZGF2aWQub3R1cyIpLCAKICAgICAgICAgICAgICAgY29sLm5hbWVzID0gYygic2FtcGxlIiwgIm90dSIsICJjb3VudCIpCiAgICAgICAgICAgICAgICkKIyBwYXJzZSBzdWJqZWN0IGFuZCB0aW1lcG9pbnRzCmRhdmlkLnNhbXBsZXMgPC0gdW5pcXVlKGRhdmlkWywgLihzYW1wbGUpXSkKZGF2aWQuc2FtcGxlc1ssIGMoInN1YmplY3QiLCAiZGF5IikgOj0gdHN0cnNwbGl0KHNhbXBsZSwgIl8iKV0KIyBsb2cgdHJhbnNmb3JtIG90dSBjb3VudHMKZGF2aWRbLCBsb2cuY291bnQgOj0gbG9nKGNvdW50ICsgMSldCiMgc3BsaXQgYnkgc3ViamVjdApkYXZpZC5zdWJqZWN0cyA8LSB1bmlxdWUoZGF2aWQuc2FtcGxlcyRzdWJqZWN0KQpuYW1lcyhkYXZpZC5zdWJqZWN0cykgPC0gZGF2aWQuc3ViamVjdHMKIyBjcmVhdGUgdGFibGVzIG9mIGRheS1kYXkgZGl2ZXJnZW5jZXMKZGF2aWQuZGl2IDwtIGRhdGEudGFibGUoZXhwYW5kLmdyaWQoc2FtcGxlLmkgPSBkYXZpZC5zYW1wbGVzJHNhbXBsZSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc2FtcGxlLmogPSBkYXZpZC5zYW1wbGVzJHNhbXBsZSkKICAgICAgICAgICAgICAgICAgICAgICAgKQpkYXZpZC5zYW1wbGVzWywgaWR4IDo9IDE6Lk5dCmRhdmlkLnNhbXBsZXNbLCBzdWJqLmlkeCA6PSBmcmFuayhhcy5udW1lcmljKGRheSkpLCBieSA9IHN1YmplY3RdCmRhdmlkLmRpdiA8LSBtZXJnZShkYXZpZC5kaXYsIGRhdmlkLnNhbXBsZXMsIGJ5LnggPSAic2FtcGxlLmkiLCAKICAgICAgICAgICAgICAgICAgIGJ5LnkgPSAic2FtcGxlIikKZGF2aWQuZGl2IDwtIG1lcmdlKGRhdmlkLmRpdiwgZGF2aWQuc2FtcGxlcywgYnkueCA9ICJzYW1wbGUuaiIsIAogICAgICAgICAgICAgICAgICAgYnkueSA9ICJzYW1wbGUiLCBzdWZmaXhlcyA9IGMoIi5pIiwgIi5qIikpCmRhdmlkLmRpdiA8LSBkYXZpZC5kaXZbaWR4LmogPj0gaWR4LmldCnNldGtleShkYXZpZCwgc2FtcGxlKQpkYXZpZC5kaXZbLCBqc2QgOj0gewogIGlmIChzYW1wbGUuaSA9PSBzYW1wbGUuaikgewogICAgMAogIH0gZWxzZSB7CiAgICBzZCA8LSBkYXZpZFtjKHNhbXBsZS5pLCBzYW1wbGUuaildCiAgICBtIDwtIGRjYXN0KHNkLCBvdHUgfiBzYW1wbGUsIHZhbHVlLnZhciA9ICJjb3VudCIpCiAgICBtIDwtIGFzLm1hdHJpeChtWywgMjozXSkKICAgIG1baXMubmEobSldIDwtIDAKICAgIGdlbkpTRChtKQogIH0KfSwgYnkgPSAuKHNhbXBsZS5pLCBzYW1wbGUuaildCiMgcmVjaXByb2NhbCBkaXN0YW5jZXMKZGF2aWQuZGl2IDwtIGRhdmlkLmRpdltzYW1wbGUuaSAhPSBzYW1wbGUual0gJT4lIAogIHNldG5hbWVzKG5hbWVzKGRhdmlkLmRpdiksIHNhcHBseShuYW1lcyhkYXZpZC5kaXYpLCBmdW5jdGlvbih4KSB7CiAgICBpZiAoZ3JlcGwoImlkeFxcLmkiLCB4KSkgewogICAgICBnc3ViKCJpZHhcXC5pIiwgImlkeFxcLmoiLCB4KQogICAgfSBlbHNlIGlmIChncmVwbCgiaWR4XFwuaiIsIHgpKSB7CiAgICAgIGdzdWIoImlkeFxcLmoiLCAiaWR4XFwuaSIsIHgpCiAgICB9IGVsc2UgaWYgKGdyZXBsKCJcXC5pIiwgeCkpIHsKICAgICAgZ3N1YigiXFwuaSIsICJcXC5qIiwgeCkKICAgIH0gZWxzZSBpZiAoZ3JlcGwoIlxcLmoiLCB4KSkgewogICAgICBnc3ViKCJcXC5qIiwgIlxcLmkiLCB4KQogICAgfSBlbHNlIHgKICB9KQogICkgJT4lICAKICByYmluZChkYXZpZC5kaXYpCmRhdmlkLmRpdlssIGRpc3RhbmNlIDo9IHNxcnQoanNkKV0KZGF2aWQuZGl2WywgZGF5LmRlbHRhIDo9IGFzLm51bWVyaWMoZGF5LmopIC0gYXMubnVtZXJpYyhkYXkuaSldCmRhdmlkLmRpdltzdWJqZWN0LmkgPT0gc3ViamVjdC5qLCBpbmNyZW1lbnQgOj0gc3Viai5pZHguaiAtIHN1YmouaWR4LmldCmBgYAoKTWVyZ2UgZXZlbnQgbWV0YWRhdGE6CmBgYHtyfQojIG1ldGFkYXRhCnNldGtleShkYXZpZC5zYW1wbGVzLCBzdWJqZWN0KQpldmVudHMgPC0gbWFwcGx5KGZ1bmN0aW9uKHN0YXJ0LCBlbmQsIHN1YmplY3QsIGV2ZW50KSB7CiAgeCA8LSBkYXRhLnRhYmxlKGRheSA9IHNlcShzdGFydCwgZW5kLCBieSA9IDEpLCBzdWJqZWN0ID0gc3ViamVjdCwgCiAgICAgICAgICAgICAgICAgIGV2ZW50ID0gZXZlbnQpCiAgeAp9LCBzdGFydCA9IGMoMCwgNzEsIDgwLCAxMDQsIDEyMywgCiAgICAgICAgICAgICAwLCAxNTEsIDE2MCApLAplbmQgPSAgIGMoNzAsIDEyMiwgODUsIDExMywgZGF2aWQuc2FtcGxlc1siQSIsIG1heChhcy5udW1lcmljKGRheSkpXSwgCiAgICAgICAgICAxNTAsIDE1OSwgZGF2aWQuc2FtcGxlc1siQiIsIG1heChhcy5udW1lcmljKGRheSkpXSksCnN1YmplY3QgPSBjKCJBIiwgIkEiLCAiQSIsICJBIiwgIkEiLCAKICAgICAgICAgICAgIkIiLCAiQiIsICJCIiksCmV2ZW50ID0gYygiVVMgKHByZSkiLCAidHJhdmVsIiwgImRpYXJyaGVhIDEiLCAiZGlhcnJoZWEgMiIsICJVUyAocG9zdCkiLCAKICAgICAgICAgICJwcmUtU2FsbW9uZWxsYSIsICJTYWxtb25lbGxhIiwgInBvc3QtU2FsbW9uZWxsYSIpLApTSU1QTElGWSA9IEZBTFNFKSAlPiUgcmJpbmRsaXN0KHVzZS5uYW1lcyA9IFRSVUUpIAojIGNvbGxhcHNlIGV2ZW50IGxhYmVscyBwZXIgZGF5CnVuaXF1ZS5kYXkuZXZlbnRzIDwtIGV2ZW50c1ssIC4oZXZlbnQgPSBwYXN0ZShldmVudCwgY29sbGFwc2UgPSAiICsgIikpLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgYnkgPSAuKHN1YmplY3QsIGRheSldCnVuaXF1ZS5kYXkuZXZlbnRzWywgZGF5IDo9IGFzLmNoYXJhY3RlcihkYXkpXQpkYXZpZC5zYW1wbGVzIDwtIG1lcmdlKGRhdmlkLnNhbXBsZXMsIHVuaXF1ZS5kYXkuZXZlbnRzLCAKICAgICAgICAgICAgICAgICAgICAgICBieSA9IGMoInN1YmplY3QiLCAiZGF5IikpCmRhdmlkLmRpdiA8LSBtZXJnZShkYXZpZC5kaXYsIHVuaXF1ZS5kYXkuZXZlbnRzLCBieS54ID0gYygic3ViamVjdC5pIiwgImRheS5pIiksCiAgICAgICAgICAgICAgICAgICBieS55ID0gYygic3ViamVjdCIsICJkYXkiKSkKZGF2aWQuZGl2IDwtIG1lcmdlKGRhdmlkLmRpdiwgdW5pcXVlLmRheS5ldmVudHMsIGJ5LnggPSBjKCJzdWJqZWN0LmoiLCAiZGF5LmoiKSwKICAgICAgICAgICAgICAgICAgIGJ5LnkgPSBjKCJzdWJqZWN0IiwgImRheSIpLCBzdWZmaXhlcyA9IGMoIi5pIiwgIi5qIikpCmBgYAoKVGhlIG1hZ25pdHVkZXMgb2YgZGF5LXRvLWRheSBjaGFuZ2VzIGluIGNvbXBvc2l0aW9uIGRvbid0IHJlZmxlY3Qgc2lnbmlmaWNhbnQgZXZlbnRzLgpgYGB7ciBkYXZpZC1zdGVwc2l6ZXMtZGF5fQpzZXRrZXkoZGF2aWQuZGl2LCBzdWJqZWN0LmksIHN1YmplY3QuaikKZXZlbnQubGltcyA8LSBldmVudHNbLCAuKHN0YXJ0ID0gbWluKGRheSksIGVuZCA9IG1heChkYXkpKSwgCiAgICAgICAgICAgICAgICAgICAgIGJ5ID0gLihldmVudCwgc3ViamVjdCldCmV2ZW50LmxpbXMgPC0gZXZlbnQubGltc1shZ3JlcGwoInByZSIsIGV2ZW50KSAmICFncmVwbCgicG9zdCIsIGV2ZW50KV0KZXZlbnQubGltc1ssIGV2ZW50IDo9IGZhY3RvcihsZXZlbHMgPSBjKCJ0cmF2ZWwiLCAiZGlhcnJoZWEgMSIsICJkaWFycmhlYSAyIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICJTYWxtb25lbGxhIiksIGV2ZW50KV0KZGF2aWQuZGl2W3N1YmplY3QuaSA9PSBzdWJqZWN0LmogJiBkYXkuZGVsdGEgPT0gMV0gJT4lIAogIG11dGF0ZShkYXkuaSA9IGFzLm51bWVyaWMoZGF5LmkpKSAlPiUgCiAgc2V0bmFtZXMoInN1YmplY3QuaSIsICJzdWJqZWN0IikgJT4lIAogIGdncGxvdChhZXMoeCA9IGRheS5pLCB5ID0gZGlzdGFuY2UpKSArCiAgZ2VvbV9yZWN0KGRhdGEgPSBldmVudC5saW1zLCAKICAgIG1hcHBpbmcgPSBhZXMoZmlsbCA9IGV2ZW50LCB4bWluID0gc3RhcnQsIHhtYXggPSBlbmQsIAogICAgICAgICAgICAgICAgICB5bWluID0gMC4xLCB5bWF4ID0gMS4wNQogICAgICAgICAgICAgICAgICApLCBpbmhlcml0LmFlcyA9IEZBTFNFLCBhbHBoYSA9IDAuNSkgKwogIGdlb21fcG9pbnQoKSArCiAgZmFjZXRfd3JhcCh+IHN1YmplY3QsIG5yb3cgPSAyKQpgYGAKCkRpc3RyaWJ1dGlvbnMgb2YgYWxsIGRpc3RhbmNlcyBmb3IgYWxsIHRpbWUgc2NhbGVzLgpXZSBzZWUgdGhhdCBib3RoIGxlbmd0aCBkaXN0cmlidXRpb25zIGFyZSBtdWx0aW1vZGFsLCBpbmRpY2F0aW5nIGF0IGxlYXN0IDIgY29tcG9zaXRpb25hbCAibGVuZ3RoIHNjYWxlcy4iCldlIGFsc28gc2VlIHRoYXQgdGhlIHZhc3QgbWFqb3JpdHkgb2YgQSBkaXN0YW5jZXMgYmVsb25nIHRvIHRoZSBsb3dlc3QgbW9kZSwgd2hpbGUgdGhlIHNlY29uZCBsb3dlc3QgbW9kZSBvZiBCIGlzIGFzIGhpZ2ggYXMgdGhlIGxvd2VzdCwgaW5kaWNhdGluZyB0aGF0IHN1YmplY3QgQiBzcGVuZHMgYSBzaWduaWZpY2FudCBhbW91bnQgb2YgdGltZSAocmVsYXRpdmUgdG8gdGhlIGxlbmd0aCBvZiB0aGUgZW50aXJlIG1lYXN1cmVtZW50KS4KYGBge3IgZGF2aWQtYWxsLWRpc3QtZGlzdHJpYixmaWcud2lkdGg9NSxmaWcuaGVpZ2h0PTV9CnAwIDwtIGdncGxvdChkYXZpZC5kaXZbc3ViamVjdC5pID09IHN1YmplY3Qual0sIGFlcyh4ID0gZGlzdGFuY2UpKSAKYXIgPC0gMyAvIDUKY2RmIDwtIHAwICsgc3RhdF9lY2RmKGFlcyhjb2xvciA9IHN1YmplY3QuaSkpICsgbGFicyh5ID0gIkVDREYiKSArCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gYXIpCmRlbnMgPC0gcDAgKyBzdGF0X2RlbnNpdHkoYWVzKGZpbGwgPSBzdWJqZWN0LmkpLCBhbHBoYSA9IDAuNSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgcG9zaXRpb24gPSAiaWRlbnRpdHkiKSArCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gYXIpCnBsb3RfZ3JpZChjZGYsIGRlbnMsIG5yb3cgPSAyLCBhbGlnbiA9ICJ2IikKYGBgCgojIyMgUGF0aHMKYGBge3IgZGF2aWQtcGF0aC1wbG90cyxmaWcud2lkdGg9NyxmaWcuaGVpZ2h0PTd9CmRhdmlkLnN1YmplY3RzIDwtIGMoIkEiLCAiQiIpCm5hbWVzKGRhdmlkLnN1YmplY3RzKSA8LSBkYXZpZC5zdWJqZWN0cwpzZXRrZXkoZGF2aWQuZGl2LCBzdWJqZWN0LmksIHN1YmplY3QuaikKZG0gPC0gTWFrZURpc3RNYXRyaXgoZGF2aWQuZGl2LCAic2FtcGxlLmkiLCAic2FtcGxlLmoiKQpmaXQgPC0gQ29vcmRDTURTKGRtKQp4Zm9ybSA8LSBmaXQkcG9pbnRzCnNldGNvbG9yZGVyKHhmb3JtLCBjKCJzYW1wbGUiLCAieCIsICJ5IikpCnNldGtleSh4Zm9ybSwgc2FtcGxlKQojIHB1dCBzYW1wbGUgbGFiZWxzIGF0IGZpcnN0IDIgY29sdW1ucwpzZXRjb2xvcmRlcihkYXZpZC5kaXYsIGMoInNhbXBsZS5pIiwgInNhbXBsZS5qIiwKICAgICAgICAgICAgICAgICAgICAgICAgIG5hbWVzKGRhdmlkLmRpdilbIShuYW1lcyhkYXZpZC5kaXYpICVpbiUKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGMoInNhbXBsZS5pIiwgInNhbXBsZS5qIikpXSkKICAgICAgICAgICAgKQpkYXZpZC5zYW1wbGVzWywgZGF5IDo9IGFzLm51bWVyaWMoZGF5KV0Kc2V0Y29sb3JkZXIoZGF2aWQuc2FtcGxlcywgYygic2FtcGxlIiwgInN1YmplY3QiLCAiZGF5IiwgImV2ZW50IiwgImlkeCIsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICJzdWJqLmlkeCIpKQpncmFmIDwtIGdyYXBoX2Zyb21fZGF0YV9mcmFtZSgKICBkYXZpZC5kaXZbc3ViamVjdC5pID09IHN1YmplY3QuaiAmIGluY3JlbWVudCA9PSAxXSwKICBkaXJlY3RlZCA9IFRSVUUsCiAgdmVydGljZXMgPSBkYXZpZC5zYW1wbGVzCiAgKQpzZXRrZXkoeGZvcm0sIHNhbXBsZSkKeGZvcm0gPC0geGZvcm1bVihncmFmKSRuYW1lXQpsbyA8LSBjcmVhdGVfbGF5b3V0KGdyYWYsICJtYW51YWwiLCBub2RlLnBvc2l0aW9ucyA9IHhmb3JtKQpuc2l6ZSA8LSAxCnAxIDwtIGdncmFwaChsbykgKwogIGdlb21fZWRnZV9saW5rKGFycm93ID0gYXJyb3cobGVuZ3RoID0gdW5pdCgzLCAicG9pbnRzIiksIHR5cGUgPSAiY2xvc2VkIiksCiAgICAgICAgICAgICAgICAgZW5kX2NhcCA9IHNxdWFyZShsZW5ndGggPSAzLCB1bml0ID0gInBvaW50cyIpLAogICAgICAgICAgICAgICAgIGVkZ2Vfd2lkdGggPSAwLjIpICsKICBnZW9tX25vZGVfcG9pbnQoYWVzKGNvbG9yID0gZGF5KSwgc2l6ZSA9IG5zaXplKSArCiAgc2NhbGVfY29sb3JfZGlzdGlsbGVyKHBhbGV0dGUgPSAiQmx1ZXMiKSArCiAgZmFjZXRfbm9kZXMofiBzdWJqZWN0KSArCiAgdGhlbWVfZ3JhcGgoYmFzZV9mYW1pbHkgPSAiSGVsdmV0aWNhIikgKwogIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEpCnAyIDwtIGdncmFwaChsbykgKwogIGdlb21fZWRnZV9saW5rKGFycm93ID0gYXJyb3cobGVuZ3RoID0gdW5pdCgzLCAicG9pbnRzIiksIHR5cGUgPSAiY2xvc2VkIiksCiAgICAgICAgICAgICAgICAgZW5kX2NhcCA9IHNxdWFyZShsZW5ndGggPSAzLCB1bml0ID0gInBvaW50cyIpLAogICAgICAgICAgICAgICAgIGVkZ2Vfd2lkdGggPSAwLjIpICsKICBnZW9tX25vZGVfcG9pbnQoYWVzKGNvbG9yID0gZXZlbnQpLCBzaXplID0gbnNpemUpICsKICBmYWNldF9ub2Rlcyh+IHN1YmplY3QpICsKICB0aGVtZV9ncmFwaChiYXNlX2ZhbWlseSA9ICJIZWx2ZXRpY2EiKSArCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkKcGxvdF9ncmlkKHAxLCBwMiwgbnJvdyA9IDIsIGFsaWduID0gInYiKQpgYGAKTGF5aW5nIGJvdGggc3ViamVjdHMgYWxvbmcgdGhlIHNhbWUgYXhlcyB3ZSBzZWUgZWFjaCBzdWJqZWN0IGlzIG1vcmUgc2ltaWxhciB0byB0aGVtc2VsdmVzIHRoYW4gdGhleSBhcmUgdG8gdGhlIG90aGVyIHN1YmplY3QsIGZvciB0aGUgbW9zdCBwYXJ0LgpUaGUgdXBwZXIgcmlnaHQgcmVwcmVzZW50cyBzdGF0ZXMgaW4gd2hpY2ggdGhlIHR3byBzdWJqZWN0cyByZXNlbWJsZWQgZWFjaCBvdGhlci4KSW50ZXJlc3RpbmdseSBub3QgYWxsIHRoZXNlIHBvaW50cyBzZWVtIHRvIGJlIGNsb3NlIGluIHRpbWUuClN1YmplY3QgQiBtYWtlcyBhIGJyaWVmIGV4Y3Vyc2lvbiB0byBhIFN1YmplY3QgQS1saWtlIHN0YXRlIHBvc3QgU2FsbW9uZWxsYS4KCkVpZ2VudmFsdWVzIGJ5IHJhbms6CmBgYHtyIGRhdmlkLWVpZ2VuLXJhbmt9CmdncGxvdChmaXQkZWlncmFuaywgYWVzKHggPSByYW5rLCB5ID0gdmFsdWUgXiAyKSkgKwogIGdlb21fcG9pbnQoKQpgYGAKCgoKIyMjIFRyZWVzCgojIyMjIFRvZ2V0aGVyCgpIaWVyYXJjaGljYWwgY2x1c3RlcmluZyByZXZlYWxzIDMgbWFqb3IgYnJhbmNoZXM6IGNoYXJhY3RlcmlzdGljIG9mIFN1YmplY3QgQSwgY2hhcmFjdGVyaXN0aWMgb2YgU3ViamVjdCBCLCBhbmQgU2hhcmVkIE91dGxpZXIgU3RhdGUuIApgYGB7ciBkYXZpZC1tZXJnZWQtdHJlZSxmaWcud2lkdGg9NyxmaWcuaGVpZ2h0PTIwfQpkbSA8LSBkY2FzdChkYXZpZC5kaXYsIHNhbXBsZS5pIH4gc2FtcGxlLmosIHZhbHVlLnZhciA9ICJkaXN0YW5jZSIpCnJuIDwtIGRtJHNhbXBsZS5pCmRtIDwtIGRtWywgLTFdCmRtIDwtIGFzLm1hdHJpeChkbSkKcm93bmFtZXMoZG0pIDwtIHJuCmRlbmRybyA8LSBhcy5kZW5kcm9ncmFtKGhjbHVzdChkaXN0KGRtKSkpCnVuaXF1ZS5kYXkuZXZlbnRzWywgZGF5IDo9IGFzLmNoYXJhY3RlcihkYXkpXQpzZXRrZXkodW5pcXVlLmRheS5ldmVudHMsIHN1YmplY3QsIGRheSkKZGF2aWQuc2FtcGxlc1ssIGRheSA6PSBhcy5jaGFyYWN0ZXIoZGF5KV0KZGF2aWQuc2FtcGxlc1ssIHN0YXRlIDo9IHsKICBzdWJqIDwtIHN1YmplY3QKICBkZCA8LSBkYXkKICB1bmlxdWUuZGF5LmV2ZW50c1suKHN1YmosIGRkKSwgZXZlbnRdCn0sIGJ5ID0gLihzdWJqZWN0LCBkYXkpXQpzZXRrZXkoZGF2aWQuc2FtcGxlcywgc2FtcGxlKQpkZW5kcm8gPC0gZGVuZHJhcHBseShkZW5kcm8sIGZ1bmN0aW9uKGQpIHsKICBpZiAoaXMubGVhZihkKSkgewogICAgc2FtcCA8LSBhdHRyKGQsICJsYWJlbCIpCiAgICBzdWJqIDwtIGRhdmlkLnNhbXBsZXNbc2FtcCwgc3ViamVjdF0KICAgIHN0YXRlIDwtIGRhdmlkLnNhbXBsZXNbc2FtcCwgc3RhdGVdCiAgICBhdHRyKGQsICJub2RlUGFyIikgPC0gYXBwZW5kKGF0dHIoZCwgIm5vZGVQYXIiKSwgbGlzdChzdWJqZWN0ID0gc3ViaiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzdGF0ZSA9IHN0YXRlKSkKICB9CiAgZAp9KQpnZ3JhcGgoZGVuZHJvLCAiZGVuZHJvZ3JhbSIpICsKICBnZW9tX2VkZ2VfZWxib3coKSArCiAgZ2VvbV9ub2RlX3BvaW50KGFlcyhmaWx0ZXIgPSBsZWFmLCBzaGFwZSA9IHN1YmplY3QsIGNvbG9yID0gc3RhdGUpLCBzaXplID0gMSkgKwogIHRoZW1lX2dyYXBoKGJhc2VfZmFtaWx5ID0gIkhlbHZldGljYSIpICsKICAjIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEpICsgCiAgY29vcmRfZmxpcCgpCmBgYAoKIyMjIyBTZXBhcmF0ZQpDbHVzdGVyaW5nIHNlcGFyYXRlbHkgc2hvd3MgdGhhdCBTdWJqZWN0IEIgaGFzIGRpc3RpbmN0IHByZS0gYW5kIHBvc3QtU2FsbW9uZWxsYSBzdGF0ZXMsIGJ1dCB0aGUgdmFyaW91cyBldmVudHMgaW4gU3ViamVjdCBBJ3MgbGlmZSBkaWRuJ3QgY3JlYXRlIGFsdGVybmF0ZSBzdGFibGUgc3RhdGVzIHRoYXQgd2VyZSBzaWduaWZpY2FudGx5IGRpZmZlcmVudC4KCmBgYHtyIGRhdmlkLWV2ZW50LXRyZWVzLGZpZy5oZWlnaHQ9OSxmaWcud2lkdGg9N30Kc2V0a2V5KGRhdmlkLmRpdiwgc3ViamVjdC5pLCBzdWJqZWN0LmopCmRlbmRyb3MgPC0gbGFwcGx5KGRhdmlkLnN1YmplY3RzLCBmdW5jdGlvbihzdWJqKSB7CiAgc2QgPC0gZGF2aWQuZGl2Wy4oc3Viaiwgc3ViaildCiAgZG0gPC0gZGNhc3Qoc2QsIHNhbXBsZS5pIH4gc2FtcGxlLmosIHZhbHVlLnZhciA9ICJkaXN0YW5jZSIpCiAgcm4gPC0gZG0kc2FtcGxlLmkKICBkbSA8LSBkbVssIC0xXQogIGRtIDwtIGFzLm1hdHJpeChkbSkKICByb3duYW1lcyhkbSkgPC0gcm4KICBoYyA8LSBoY2x1c3QoZGlzdChkbSkpCiAgZGVuZHJvIDwtIGFzLmRlbmRyb2dyYW0oaGMpCiAgcmV0dXJuKGRlbmRybykKfQopCnVuaXF1ZS5kYXkuZXZlbnRzWywgZGF5IDo9IGFzLmNoYXJhY3RlcihkYXkpXQojIHNldGtleShldmVudHMsIHN1YmplY3QpCnNldGtleSh1bmlxdWUuZGF5LmV2ZW50cywgc3ViamVjdCwgZGF5KQpzZXRrZXkoZGF2aWQuc2FtcGxlcywgc2FtcGxlKQpkZW5kcm9zIDwtIGxhcHBseShkYXZpZC5zdWJqZWN0cywgZnVuY3Rpb24oc3ViaikgewogIGRlbmRybyA8LSBkZW5kcm9zW1tzdWJqXV0KICBkZW5kcm8gPC0gZGVuZHJhcHBseShkZW5kcm8sIGZ1bmN0aW9uKGQpIHsKICAgIGlmIChpcy5sZWFmKGQpKSB7CiAgICAgIGRkYXkgPC0gZGF2aWQuc2FtcGxlc1thdHRyKGQsICJsYWJlbCIpLCBhcy5jaGFyYWN0ZXIoZGF5KV0KICAgICAgZXYgPC0gdW5pcXVlLmRheS5ldmVudHNbLihzdWJqLCBkZGF5KSwgZXZlbnRdCiAgICAgIGF0dHIoZCwgIm5vZGVQYXIiKSA8LSBhcHBlbmQoYXR0cihkLCAibm9kZVBhciIpLCBsaXN0KAogICAgICAgIGRheSA9IGFzLm51bWVyaWMoZGRheSksCiAgICAgICAgZXZlbnQgPSBldikpCiAgICB9CiAgICBkCiAgfSkKICAjIHByb3BhZ2F0ZSBtZXRhZGF0YSBiYWNrIHVwIHRoZSB0cmVlCiAgZGVuZHJvIDwtIHRyZWVfYXBwbHkoZGVuZHJvLCBmdW5jdGlvbihub2RlLCBjaGlsZHJlbiwgZGVwdGgsIHRyZWUpIHsKICBpZiAoIWlzLmxlYWYobm9kZSkpIHsKICAgIGV2ZW50cyA8LSBzYXBwbHkoY2hpbGRyZW4sIGZ1bmN0aW9uKGMpIHsKICAgICAgYXR0cihjLCAibm9kZVBhciIpJGV2ZW50CiAgICB9KQogICAgZXZlbnRzIDwtIHVuaXF1ZShldmVudHMpCiAgICBpZiAobGVuZ3RoKGV2ZW50cykgPT0gMSAmICFhbnlOQShldmVudHMpKSB7CiAgICAgIGF0dHIobm9kZSwgIm5vZGVQYXIiKSA8LSBhcHBlbmQoYXR0cihub2RlLCAibm9kZVBhciIpLCBsaXN0KGV2ZW50ID0gZXZlbnRzKSkKICAgIH0gZWxzZSB7CiAgICAgIGF0dHIobm9kZSwgIm5vZGVQYXIiKSA8LSBhcHBlbmQoYXR0cihub2RlLCAibm9kZVBhciIpLCBsaXN0KGV2ZW50ID0gTkEpKQogICAgfQogIH0KICBub2RlCiAgfSwgZGlyZWN0aW9uID0gInVwIikKICBkZW5kcm8KfSkKZGVuZHJvLnBsb3RzIDwtIGxhcHBseShkZW5kcm9zLCBmdW5jdGlvbihkZW5kKSB7CiAgZ2dyYXBoKGRlbmQsICJkZW5kcm9ncmFtIiwgY2lyY3VsYXIgPSBUUlVFKSArCiAgICBnZW9tX2VkZ2VfZWxib3coYWVzKGNvbG9yID0gbm9kZTIuZXZlbnQpKSArCiAgICBnZW9tX25vZGVfcG9pbnQoYWVzKGZpbHRlciA9IGxlYWYsIGNvbG9yID0gZGF5KSwgc2l6ZSA9IDAuNikgKwogICAgc2NhbGVfY29sb3JfZGlzdGlsbGVyKHBhbGV0dGUgPSAiU3BlY3RyYWwiKSArCiAgICB0aGVtZV9ncmFwaChiYXNlX2ZhbWlseSA9ICJIZWx2ZXRpY2EiKSArCiAgICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKQp9KQpwbG90X2dyaWQocGxvdGxpc3QgPSBkZW5kcm8ucGxvdHMsIG5yb3cgPSAyLCBsYWJlbHMgPSAiQVVUTyIpCmBgYAoKU3ViamVjdCBBIGRvZXNuJ3Qgc2VlbSB0byBoYXZlIGEgZGlzdGluY3QgInRyYXZlbGluZyIgY29tcG9zaXRpb24uCkluZGVlZCBpdCBzZWVtcyB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0cmF2ZWxpbmcgYW5kIFVTIGNvbXBvc2l0aW9ucyBkb2Vzbid0IHNlZW0gbm90aWNlYWJseSBsYXJnZXIgdGhhbiB0aGUgZGlzdGFuY2UgYmV0d2VlbiBVUyBjb21wb3NpdGlvbnMuCk1lYW5pbmcgdHJhdmVsaW5nIGRpZCBub3QgZGVzdGFiaWxpemUgdGhlIG1pY3JvYmlvbWUgYW55IG1vcmUgdGhhbiBiYXNlbGluZSBmbHVjdHVhdGlvbnMgd2hpbGUgbGl2aW5nIGluIHRoZSBVUy4KUGVyaGFwcyB0aGlzIGlzIGR1ZSB0byBtYW55IE9UVXMgcmVtYWluaW5nIHN0YWJsZSB0aHJvdWdoIHRoZSBkdXJhdGlvbiBvZiB0cmF2ZWwuCgpTdWJqZWN0IEIgc2hvd3MgY2xlYXIgcHJlLSBhbmQgcG9zdC1TYWxtb25lbGxhIHN0YXRlcywgYXMgcmVwb3J0ZWQgaW4gdGhlIG9yaWdpbmFsIG1hbnVzY3JpcHQuClBlcmhhcHMgdGhlIHBvc3QtU2FsbW9uZWxsYSBzdGF0ZSBpcyBzZXBhcmF0ZSBiZWNhdXNlIG9mIHRoZSBleHRpbmN0aW9uIG9mIGNsdXN0ZXIgNCAoc2VlIG9yaWdpbmFsIHBhcGVyKSBkdXJpbmcgaW5mZWN0aW9uLCByZW5kZXJpbmcgcmV0dXJuIHRvIHRoZSBwcmUtU2FsbW9uZWxsYSBzdGF0ZSBpbXBvc3NpYmxlPwoKIyMgR29yZG9uIGV0IGFsIChjaG9sZXJhKQpgYGB7cn0KZ29yZG9uIDwtIGZyZWFkKHBhc3RlMChkYXRhLmRpciwgImNob2xlcmEvZ29yZG9uLm90dXMiKSwKICAgICAgICAgICAgICAgIGNvbC5uYW1lcyA9IGMoInNhbXBsZSIsICJvdHUiLCAiY291bnQiKSkKIyBleHRyYWN0IHNhbXBsZSBpbmZvCmdvcmRvbi5zYW1wbGVzIDwtIHVuaXF1ZShnb3Jkb25bLCAuKHNhbXBsZSldKQojIGNyZWF0ZSBhIGR1bW15ICdzYW1wbGUgaW5kZXgnIHRvIGhlbHAgcmVtb3ZlIHJlY2lwcm9jYWwgc2FtcGxlIHBhaXJzIGxhdGVyIApnb3Jkb24uc2FtcGxlc1ssIGlkeCA6PSAxOi5OXQpnb3Jkb24uc2FtcGxlc1ssIGMoInN1YmplY3QiLCAic3RhdGUiLCAiaWQiKSA6PSB0c3Ryc3BsaXQoc2FtcGxlLCAiXyIpXQpnb3Jkb24uc2FtcGxlc1tncmVwKCJkIiwgaWQpICYgc3RhdGUgPT0gInJlY292ZXJ5IiwgdGltZS51bml0IDo9ICJkYXkiXQpnb3Jkb24uc2FtcGxlc1shZ3JlcCgiZCIsIGlkKSwgdGltZS51bml0IDo9ICJob3VyIl0KZ29yZG9uLnNhbXBsZXNbaWQgPT0gImVuZCIsIHRpbWUudW5pdCA6PSAiaG91ciJdCnNldGtleShnb3Jkb24uc2FtcGxlcywgdGltZS51bml0KQpnb3Jkb24uc2FtcGxlc1siaG91ciIsIGhvdXIgOj0gYXMubnVtZXJpYyhpZCldCmdvcmRvbi5zYW1wbGVzWyJkYXkiLCBob3VyIDo9IDI0ICogYXMubnVtZXJpYyhzdWIoImQiLCAiIiwgaWQpKV0Kc3ViamVjdHMgPC0gdW5pcXVlKGdvcmRvbi5zYW1wbGVzJHN1YmplY3QpCiMgc2V0IGVuZCBob3VyIHRvIGxhc3QgaG91ciArIDEsIGRheXMgdG8gZW5kIGhvdXIgKyAyNCAqIGRheXMKZ29yZG9uLnNhbXBsZXNbLCBob3VyIDo9IHsKICBtYXhociA8LSBtYXgoLlNEWyJob3VyIl1baWQgIT0gImVuZCJdJGhvdXIpCiAgZW5kaHIgPC0gbWF4aHIgKyAxCiAgaG91cltpZCA9PSAiZW5kIl0gPC0gZW5kaHIKICBob3VyW3RpbWUudW5pdCA9PSAiZGF5Il0gPC0gaG91clt0aW1lLnVuaXQgPT0gImRheSJdICsgZW5kaHIKICBob3VyCn0sIGJ5ID0gc3ViamVjdF0KIyBhbGwgc2FtcGxlcyB2cyBhbGwgc2FtcGxlcwpnb3Jkb24uZGl2IDwtIGRhdGEudGFibGUoZXhwYW5kLmdyaWQoc2FtcGxlLmkgPSBnb3Jkb24uc2FtcGxlcyRzYW1wbGUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzYW1wbGUuaiA9IGdvcmRvbi5zYW1wbGVzJHNhbXBsZSkKICAgICAgICAgICAgICAgICAgICAgICAgICkKIyBtZXJnZSBzYW1wbGUgaW5mbwpnb3Jkb24uZGl2IDwtIG1lcmdlKGdvcmRvbi5kaXYsIGdvcmRvbi5zYW1wbGVzLCBieS54ID0gInNhbXBsZS5pIiwgCiAgICAgICAgICAgICAgICAgICAgYnkueSA9ICJzYW1wbGUiCiAgICAgICAgICAgICAgICAgICAgKQpnb3Jkb24uZGl2IDwtIG1lcmdlKGdvcmRvbi5kaXYsIGdvcmRvbi5zYW1wbGVzLCBieS54ID0gInNhbXBsZS5qIiwgCiAgICAgICAgICAgICAgICAgICAgYnkueSA9ICJzYW1wbGUiLCBzdWZmaXhlcyA9IGMoIi5pIiwgIi5qIikKICAgICAgICAgICAgICAgICAgICApCiMgcmVtb3ZlIGludmVyc2UgcGFpcmluZ3MKZ29yZG9uLmRpdiA8LSBnb3Jkb24uZGl2W2lkeC5qID49IGlkeC5pXQojIHJlbW92ZSBkdW1teSB2YXJpYWJsZQpnb3Jkb24uZGl2WywgIjo9IiAoaWR4LmkgPSBOVUxMLCBpZHguaiA9IE5VTEwpXQpnb3Jkb25bLCBsb2cuY291bnQgOj0gbG9nKGNvdW50KV0KZ29yZG9uCnNldGtleShnb3Jkb24sIHNhbXBsZSkKZ29yZG9uLmRpdlssIGpzZCA6PSB7CiAgaWYgKHNhbXBsZS5pID09IHNhbXBsZS5qKSB7CiAgICAwCiAgfSBlbHNlewogICAgc2kgPC0gc2FtcGxlLmkKICAgIHNqIDwtIHNhbXBsZS5qCiAgICBzZCA8LSBnb3Jkb25bYyhzaSwgc2opXQogICAgbSA8LSBkY2FzdChzZCwgb3R1IH4gc2FtcGxlLCB2YWx1ZS52YXIgPSAiY291bnQiKQogICAgbSA8LSBhcy5tYXRyaXgobVssIDI6M10pCiAgICBtW2lzLm5hKG0pXSA8LSAwCiAgICBnZW5KU0QobSkKICB9Cn0sIGJ5ID0gLihzYW1wbGUuaSwgc2FtcGxlLmopXQppbnYgPC0gZ29yZG9uLmRpdltzYW1wbGUuaSAhPSBzYW1wbGUual0Kc2V0bmFtZXMoaW52LCBuYW1lcyhpbnYpLCBzYXBwbHkobmFtZXMoaW52KSwgZnVuY3Rpb24oeCkgewogIGlmIChncmVwbCgiXFwuaSIsIHgpKSB7CiAgICBnc3ViKCJcXC5pIiwgIlxcLmoiLCB4KQogIH0gZWxzZSBpZiAoZ3JlcGwoIlxcLmoiLCB4KSkgewogICAgZ3N1YigiXFwuaiIsICJcXC5pIiwgeCkKICB9IGVsc2UgewogICAgeAogIH0KfSkpCmdvcmRvbi5kaXYgPC0gcmJpbmQoZ29yZG9uLmRpdiwgaW52KQpnb3Jkb24uZGl2WywgZGlzdGFuY2UgOj0gc3FydChqc2QpXQpgYGAKCkRhdmlkLXN0eWxlIGRpdmVyZ2VuY2UgbWF0cmljZXMuCkRhcmsgb24tZGlhZ29uYWwgc3F1YXJlcyByZXByZXNlbnQgb2NjdXBhdGlvbiBvZiBzdGFibGUgc3RhdGVzLgpNb3N0IHBhdGllbnRzIGhhdmUgZGlzdGluY3Qgc3RhYmxlIHN0YXRlcy4KYGBge3IgZ29yZG9uLWRpdi1tYXRyaWNlcyxmaWcud2lkdGg9NyxmaWcuaGVpZ2h0PTd9CnNldGtleShnb3Jkb24uZGl2LCBzdWJqZWN0LmksIHN1YmplY3QuaikKc3ViamVjdHMgPC0gc29ydChzdWJqZWN0cykKbmFtZXMoc3ViamVjdHMpIDwtIHN1YmplY3RzCmdvcmRvbi5kaXZbLCAiOj0iIChob3VyLmkgPSBhcy5jaGFyYWN0ZXIoaG91ci5pKSwgaG91ci5qID0gYXMuY2hhcmFjdGVyKGhvdXIuaikpXQpwbG90cyA8LSBsYXBwbHkoc3ViamVjdHMsIGZ1bmN0aW9uKHN1YmopIHsKICBzZCA8LSBnb3Jkb24uZGl2Wy4oc3Viaiwgc3ViaildCiAgdHMgPC0gYXMubnVtZXJpYyh1bmlxdWUoc2QkaG91ci5pKSkKICBsaW1zIDwtIGFzLmNoYXJhY3Rlcihzb3J0KHRzKSkKICBwIDwtIGdncGxvdChzZCwgYWVzKHggPSBob3VyLmksIHkgPSBob3VyLmopKSArCiAgICBnZW9tX3RpbGUoYWVzKGZpbGwgPSBqc2QpKSArCiAgICBzY2FsZV94X2Rpc2NyZXRlKGxpbWl0cyA9IGxpbXMpICsKICAgIHNjYWxlX3lfZGlzY3JldGUobGltaXRzID0gbGltcykgKwogICAgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSwKICAgICAgICAgIGF4aXMudGV4dCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICAgIGF4aXMudGlja3MgPSBlbGVtZW50X2JsYW5rKCkpCn0pCnBsb3RfZ3JpZChwbG90bGlzdCA9IHBsb3RzLCBuY29sID0gMiwgbGFiZWxzID0gbmFtZXMocGxvdHMpLCBhbGlnbiA9ICJodiIpCmBgYAoKVGltZS1sYWcgZGl2ZXJnZW5jZXM6CmBgYHtyIGdvcmRvbi1sYWctanNkfQpnb3Jkb24uZGl2WywgZGVsdGEudCA6PSBhcy5udW1lcmljKGhvdXIuaikgLSBhcy5udW1lcmljKGhvdXIuaSldCnBsb3RzIDwtIGxhcHBseShzdWJqZWN0cywgZnVuY3Rpb24oc3ViaikgewogIHNkIDwtIGdvcmRvbi5kaXZbLihzdWJqLCBzdWJqKV0KICBzZCA8LSBzZFtkZWx0YS50ID4gMF0KICBwIDwtIGdncGxvdChzZCwgYWVzKHggPSBkZWx0YS50LCB5ID0ganNkKSkgKwogICAgZ2VvbV9wb2ludChzaXplID0gMC4xKSArCiAgICBnZW9tX3Ntb290aChjb2xvciA9ICJibHVlIikgKwogICAgc2NhbGVfeF9sb2cxMCgpICsKICAgIGxhYnMoeCA9ICJsYWcgKGhvdXJzKSIpCiAgcAp9KQpwbG90X2dyaWQocGxvdGxpc3QgPSBwbG90cywgYWxpZ24gPSAiaHYiLCBsYWJlbHMgPSBuYW1lcyhwbG90cyksCiAgICAgICAgICBucm93ID0gMykKYGBgCgpEaXN0cmlidXRpb25zIG9mIGRpdmVyZ2VuY2VzIHNob3cgdGhhdCBmb3IgYWxsIHBhdGllbnRzLCBkaWFycmhlYSBhbmQgcmVjb3Zlcnkgc3RhdGVzIGFyZSBtb3JlIHNpbWlsYXIgdG8gdGhlbXNlbHZlcyB0aGFuIHRvIGVhY2ggb3RoZXIgKGNyb3NzLXN0YXRlIGRpdmVyZ2VuY2VzIGFyZSBsYXJnZSkuCkluIG1vc3QgcGF0aWVudHMgKGV4Y2VwdCBFKSB0aGUgcmVjb3ZlcnkgbWljcm9iaW9tZSBpcyBhY3R1YWxseSBsZXNzIHN0YWJsZSB0aGFuIHRoZSBkaWFycmhlYSBtaWNyb2Jpb21lOiB0aGUgZGlhcnJoZWEgZGl2ZXJnZW5jZXMgdGVuZCB0byBiZSBzbWFsbGVyLgoqKkhvd2V2ZXIqKiB0aGlzIGNvdWxkIGFsc28gYmUgZHVlIHRvIHRoZSBkZW5zZXIgdGVtcG9yYWwgc2FtcGxpbmcgZHVyaW5nIHRoZSBkaWFycmhlYSBwZXJpb2QuCldlIHNob3VsZCBzY2FsZSB0aGlzIGJ5IHRoZSB0aW1lIGludGVydmFsIHNvbWVob3csIHNpbmNlIGl0IHZhcmllcy4KYGBge3IgZ29yZG9uLWRpc3QtZGlzdHJpYn0KZ29yZG9uLmRpdlssIHN0YXRlIDo9IHsKICBpZiAoc3RhdGUuaSA9PSBzdGF0ZS5qKSBzdGF0ZS5pCiAgZWxzZSAiY3Jvc3MiCn0sIGJ5ID0gLihzdGF0ZS5pLCBzdGF0ZS5qKV0gIApwMCA8LSBnb3Jkb24uZGl2WyhzdWJqZWN0LmkgPT0gc3ViamVjdC5qKSAmIChkZWx0YS50ID4gMCldICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBkaXN0YW5jZSkpCmNkZiA8LSBwMCArIHN0YXRfZWNkZihhZXMoY29sb3IgPSBzdGF0ZSkpICsgZmFjZXRfd3JhcCh+IHN1YmplY3QuaSwgbnJvdyA9IDEpICsgCiAgbGFicyh5ID0gIkVDREYiKSArCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA5MCwgdmp1c3QgPSAwLjUsIGhqdXN0ID0gMSkpCmRlbnMgPC0gcDAgKyBzdGF0X2RlbnNpdHkoYWVzKGZpbGwgPSBzdGF0ZSksIGFscGhhID0gMC4zLAogICAgICAgICAgICAgICAgICAgICAgICAgIHBvc2l0aW9uID0gImlkZW50aXR5IikKZGVucyA8LSBkZW5zICsKICBmYWNldF93cmFwKH4gc3ViamVjdC5pLCBucm93ID0gMSkgKwogIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gOTAsIHZqdXN0ID0gMC41LCBoanVzdCA9IDEpKQpwbG90X2dyaWQoY2RmLCBkZW5zLCBucm93ID0gMiwgYWxpZ24gPSAidiIpCmBgYAoKIyMjIFBhdGhzCk1EUyBvZiBhbGwgc3ViamVjdHMgc2ltdWx0YW5lb3VzbHkgc2hvd3MgdGhhdCBkaWFycmhlYS9yZWNvdmVyeSBzZXBhcmF0ZXMgdGltZSBwb2ludHMgbW9yZSB0aGFuIHN1YmplY3QuCmBgYHtyIGdvcmRvbi1wYXRoc30Kc2V0a2V5KGdvcmRvbi5kaXYsIHN1YmplY3QuaSwgc3ViamVjdC5qKQpzZXRrZXkoZ29yZG9uLnNhbXBsZXMsIHN1YmplY3QpCmVkZ2VzIDwtIGxhcHBseShzdWJqZWN0cywgZnVuY3Rpb24oc3ViaikgewogIHNkIDwtIGdvcmRvbi5kaXZbLihzdWJqLCBzdWJqKV0KICB0cyA8LSBhcy5udW1lcmljKHVuaXF1ZShzZCRob3VyLmkpKQogIHRzIDwtIGFzLmNoYXJhY3Rlcihzb3J0KHRzKSkKICBlaiA8LSBkYXRhLnRhYmxlKHRpID0gdHNbLWxlbmd0aCh0cyldLCB0aiA9IHRzWy0xXSkKICBzYW1wcyA8LSBnb3Jkb24uc2FtcGxlc1tzdWJqLCAuKHNhbXBsZSwgaG91cildCiAgc2FtcHNbLCBob3VyIDo9IGFzLmNoYXJhY3Rlcihob3VyKV0KICBlaiA8LSBtZXJnZShlaiwgc2FtcHMsIGJ5LnggPSAidGkiLCBieS55ID0gImhvdXIiKQogIGVqIDwtIG1lcmdlKGVqLCBzYW1wcywgYnkueCA9ICJ0aiIsIGJ5LnkgPSAiaG91ciIsIHN1ZmZpeGVzID0gYygiLmkiLCAiLmoiKSkKICBlalssIC4oc2FtcGxlLmksIHNhbXBsZS5qKV0KfSkgJT4lIHJiaW5kbGlzdCgpCmdyYWYgPC0gZ3JhcGhfZnJvbV9kYXRhX2ZyYW1lKGVkZ2VzLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkaXJlY3RlZCA9IFRSVUUsIHZlcnRpY2VzID0gZ29yZG9uLnNhbXBsZXMpCmRtIDwtIE1ha2VEaXN0TWF0cml4KGdvcmRvbi5kaXYsICJzYW1wbGUuaSIsICJzYW1wbGUuaiIpCmZpdCA8LSBDb29yZENNRFMoZG0pCnhmb3JtIDwtIGZpdCRwb2ludHMKIyBvcmRlcgpzZXRrZXkoeGZvcm0sIHNhbXBsZSkKeGZvcm0gPC0geGZvcm1bVihncmFmKSRuYW1lXQpsbyA8LSBjcmVhdGVfbGF5b3V0KGdyYWYsICJtYW51YWwiLCBub2RlLnBvc2l0aW9ucyA9IHhmb3JtKQpnZ3JhcGgobG8pICsKICBnZW9tX2VkZ2VfbGluayhhcnJvdyA9IGFycm93KHR5cGUgPSAiY2xvc2VkIiwgbGVuZ3RoID0gdW5pdCgzLCAicG9pbnRzIikpLAogICAgICAgICAgICAgICAgIGVkZ2Vfd2lkdGggPSAwLjIsIGVuZF9jYXAgPSBzcXVhcmUobGVuZ3RoID0gMywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHVuaXQgPSAicG9pbnRzIikpICsKICBnZW9tX25vZGVfcG9pbnQoYWVzKGNvbG9yID0gc3RhdGUpKSArCiAgIyBzY2FsZV9zaGFwZV9tYW51YWwodmFsdWVzID0gc2VxKDEsIGxlbmd0aChzdWJqZWN0cykpKSArCiAgZmFjZXRfbm9kZXMofiBzdWJqZWN0LCBucm93ID0gMikgKwogIHRoZW1lX2dyYXBoKGJhc2VfZmFtaWx5ID0gIkhlbHZldGljYSIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKQpnZ3Bsb3QoZml0JGVpZ3JhbmssIGFlcyh4ID0gcmFuaywgeSA9IHZhbHVlIF4gMikpICsKICBnZW9tX3BvaW50KCkgCmBgYAoKQWxsIHBvaW50cyBwbG90IHNob3cgcmVjb3ZlcnkgYW5kIGRpYXJyaGVhIGNsdXN0ZXIgc2VwYXJhdGVseSBmb3IgYWxsIHBhdGllbnRzLCB3aXRoIGRpYXJyaGVhIGhhdmluZyBncmVhdGVyIHNwcmVhZDoKYGBge3J9CmdncmFwaChsbykgKwogIGdlb21fbm9kZV9wb2ludChhZXMoY29sb3IgPSBzdGF0ZSwgc2hhcGUgPSBzdWJqZWN0KSkgKwogIHNjYWxlX3NoYXBlX21hbnVhbCh2YWx1ZXMgPSBzZXEodW5pcXVlTihnb3Jkb24uc2FtcGxlcyRzdWJqZWN0KSkpICsKICB0aGVtZV9ncmFwaChiYXNlX2ZhbWlseSA9ICJIZWx2ZXRpY2EiKSArCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkKYGBgCgojIyMgVHJlZQoKQWxsIHRvZ2V0aGVyLgpBZ2FpbiBzZXBhcmF0aW9uIGlzIG1vc3RseSBkaWFycmhlYS9yZWNvdmVyeS4KSG93ZXZlciwgc29tZSBkaWFycmhlYSBwb2ludHMgYXJlIGNsb3NlciB0byByZWNvdmVyeSBwb2ludHMgdGhhbiB0aGV5IGFyZSB0byB0aGUgbWFqb3JpdHkgb2YgZGlhcnJoZWEgcG9pbnRzLgpUaGlzIGNhbiBhbHNvIGJlIHNlZW4gaW4gdGhlIGxhc3QgcGxvdCB3aGVyZSB0aGUgdHdvICdjbG91ZHMnIGVubWVzaC4KYGBge3IsZmlnLndpZHRoPTcsZmlnLmhlaWdodD03fQpkbSA8LSBkY2FzdChnb3Jkb24uZGl2LCBzYW1wbGUuaSB+IHNhbXBsZS5qLCB2YWx1ZS52YXIgPSAiZGlzdGFuY2UiKQpybiA8LSBkbVssIHNhbXBsZS5pXSAKZG0gPC0gYXMubWF0cml4KGRtWywgLTFdKQpyb3duYW1lcyhkbSkgPC0gcm4KZGVuZHJvIDwtIGFzLmRlbmRyb2dyYW0oaGNsdXN0KGRpc3QoZG0pKSkKIyBhbm5vdGF0ZQpzZXRrZXkoZ29yZG9uLnNhbXBsZXMsIHNhbXBsZSkKZGVuZHJvIDwtIGRlbmRyYXBwbHkoZGVuZHJvLCBmdW5jdGlvbihkKSB7CiAgaWYgKGlzLmxlYWYoZCkpIHsKICAgIHNhbXAuaWQgPC0gYXR0cihkLCAibGFiZWwiKQogICAgc2FtcGxlIDwtIGdvcmRvbi5zYW1wbGVzW3NhbXAuaWRdCiAgICBzdWJqIDwtIHNhbXBsZSRzdWJqZWN0CiAgICBzdGF0ZSA8LSBzYW1wbGUkc3RhdGUKICAgIGF0dHIoZCwgIm5vZGVQYXIiKSA8LSBhcHBlbmQoYXR0cihkLCAibm9kZVBhciIpLCBsaXN0KHN1YmplY3QgPSBzdWJqLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc3RhdGUgPSBzdGF0ZSkpCiAgfQogIGQKfSkKbG8gPC0gY3JlYXRlX2xheW91dChkZW5kcm8sICJkZW5kcm9ncmFtIiwgY2lyY3VsYXIgPSBUUlVFKQpnZ3JhcGgobG8pICsKICBnZW9tX2VkZ2VfZWxib3coKSArCiAgZ2VvbV9ub2RlX3BvaW50KGFlcyhmaWx0ZXIgPSBsZWFmLCBzaGFwZSA9IHN1YmplY3QsIGNvbG9yID0gc3RhdGUpKSArCiAgc2NhbGVfc2hhcGVfbWFudWFsKHZhbHVlcyA9IHNlcSgxLCBsZW5ndGgoc3ViamVjdHMpKSkgKwogIHRoZW1lX2dyYXBoKGJhc2VfZmFtaWx5ID0gIkhlbHZldGljYSIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKQpgYGAKCmBgYHtyIGdvcmRvbi1zdGF0ZS1jbHVzdGVycyxmaWcud2lkdGg9NyxmaWcuaGVpZ2h0PTEwfQpzZXRrZXkoZ29yZG9uLmRpdiwgc3ViamVjdC5pLCBzdWJqZWN0LmopCmdvcmRvbi5zYW1wbGVzWywgaG91ciA6PSBhcy5jaGFyYWN0ZXIoaG91cildCnNldGtleShnb3Jkb24uc2FtcGxlcywgc3ViamVjdCwgaG91cikKdHJlZXMgPC0gbGFwcGx5KHN1YmplY3RzLCBmdW5jdGlvbihzdWJqKSB7CiAgc2QgPC0gZ29yZG9uLmRpdlsuKHN1YmosIHN1YmopXQogIHNkIDwtIGRjYXN0KHNkLCBob3VyLmkgfiBob3VyLmosIHZhbHVlLnZhciA9ICJkaXN0YW5jZSIpCiAgcm4gPC0gc2RbLCBob3VyLmldCiAgZG0gPC0gYXMubWF0cml4KHNkWywgLTFdKQogIHJvd25hbWVzKGRtKSA8LSBybgogIGRlbmRybyA8LSBhcy5kZW5kcm9ncmFtKGhjbHVzdChkaXN0KGRtKSkpCiAgIyBtZXJnZSB0aW1lIGRhdGEgYW5kIHN0YXRlCiAgc2RbLCB0aW1lLmluZGV4IDo9IGZyYW5rKGFzLm51bWVyaWMoaG91ci5pKSldCiAgc2V0a2V5KHNkLCBob3VyLmkpCiAgZGVuZHJvIDwtIGRlbmRyYXBwbHkoZGVuZHJvLCBmdW5jdGlvbihub2RlKSB7CiAgICBpZiAoaXMubGVhZihub2RlKSkgewogICAgICBsYWJsIDwtIGF0dHIobm9kZSwgImxhYmVsIikKICAgICAgdCA8LSBhcy5udW1lcmljKGxhYmwpCiAgICAgIHRpbWUuaW5kZXggPC0gYXMubnVtZXJpYyhzZFtsYWJsLCB0aW1lLmluZGV4XSkKICAgICAgc3RhdGUgPC0gZ29yZG9uLnNhbXBsZXNbLihzdWJqLCBsYWJsKSwgc3RhdGVdCiAgICAgIGF0dHIobm9kZSwgIm5vZGVQYXIiKSA8LSBhcHBlbmQoYXR0cihub2RlLCAibm9kZVBhciIpLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsaXN0KGhvdXIgPSB0LCB0aW1lLmluZGV4ID0gdGltZS5pbmRleCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN0YXRlID0gc3RhdGUpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKQogICAgfQogICAgbm9kZQogIH0pCiAgIyBwcm9wYWdhdGUgc3RhdGUgdXB3YXJkcyB0aHJvdWdoIGJyYW5jaCBub2RlcwogIGRlbmRybyA8LSB0cmVlX2FwcGx5KGRlbmRybywgZnVuY3Rpb24obm9kZSwgdHJlZSwgZGVwdGgsIGNoaWxkcmVuKSB7CiAgICBpZiAoIWlzLmxlYWYobm9kZSkpIHsKICAgICAgY2hpbGQuc3RhdGVzIDwtIHNhcHBseShjaGlsZHJlbiwgZnVuY3Rpb24obikgewogICAgICAgIGF0dHIobiwgIm5vZGVQYXIiKSRzdGF0ZQogICAgICB9KSAlPiUgdW5pcXVlKCkKICAgICAgaWYgKGxlbmd0aChjaGlsZC5zdGF0ZXMpID09IDEgJiAhYW55TkEoY2hpbGQuc3RhdGVzKSkgewogICAgICAgIHN0YXRlIDwtIGNoaWxkLnN0YXRlcwogICAgICB9IGVsc2UgewogICAgICAgIHN0YXRlIDwtIE5BCiAgICAgIH0KICAgICAgYXR0cihub2RlLCAibm9kZVBhciIpIDwtIGFwcGVuZChhdHRyKG5vZGUsICJub2RlUGFyIiksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbGlzdChzdGF0ZSA9IHN0YXRlKSkKICAgIH0KICAgIG5vZGUKICB9LCBkaXJlY3Rpb24gPSAidXAiKQogICMgYnJvd3NlcigpCiAgcCA8LSBnZ3JhcGgoZGVuZHJvLCAiZGVuZHJvZ3JhbSIsIGNpcmN1bGFyID0gVFJVRSkgKwogICAgZ2VvbV9lZGdlX2VsYm93KGFlcyhjb2xvciA9IG5vZGUyLnN0YXRlKSkgKwogICAgZ2VvbV9ub2RlX3BvaW50KGFlcyhmaWx0ZXIgPSBsZWFmLCBjb2xvciA9IHRpbWUuaW5kZXgpKSArCiAgICBzY2FsZV9jb2xvcl9kaXN0aWxsZXIocGFsZXR0ZSA9ICJZbE9yUmQiKSArCiAgICB0aGVtZV9ncmFwaChiYXNlX2ZhbWlseSA9ICJIZWx2ZXRpY2EiKSArCiAgICB0aGVtZShhc3BlY3QucmF0aW8gPSAxLCBsZWdlbmQua2V5LmhlaWdodCA9IHVuaXQoMTAsICJwb2ludHMiKSkKfSkKcGxvdF9ncmlkKHBsb3RsaXN0ID0gdHJlZXMsIG5jb2wgPSAyLCBsYWJlbHMgPSBuYW1lcyh0cmVlcykpCmBgYAoK